2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
#include <cstdio>
#include <queue>
using namespace std;
int a[100][100];
int g[100][100];
int d[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int n;
scanf("%d",&n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
scanf("%d",&a[i][j]);
}
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 1 && g[i][j] == 0) {
g[i][j] = ++cnt;
queue<pair<int,int>> q;
q.push(make_pair(i,j));
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (a[nx][ny] == 1 && g[nx][ny] == 0) {
g[nx][ny] = cnt;
q.push(make_pair(nx,ny));
}
}
}
}
}
}
}
int ans = -1;
for (int l=1; l<=cnt; l++) {
queue<pair<int,int>> q;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
d[i][j] = -1;
if (g[i][j] == l) {
q.push(make_pair(i,j));
d[i][j] = 0;
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push(make_pair(nx,ny));
}
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 1 && g[i][j] != l) {
if (ans == -1 || d[i][j]-1 < ans) {
ans = d[i][j]-1;
}
}
}
}
}
printf("%d\n",ans);
return 0;
}
#include <cstdio>
#include <queue>
using namespace std;
int a[100][100];
int g[100][100];
int d[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int n;
scanf("%d",&n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
scanf("%d",&a[i][j]);
}
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 1 && g[i][j] == 0) {
g[i][j] = ++cnt;
queue<pair<int,int>> q;
q.push(make_pair(i,j));
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (a[nx][ny] == 1 && g[nx][ny] == 0) {
g[nx][ny] = cnt;
q.push(make_pair(nx,ny));
}
}
}
}
}
}
}
queue<pair<int,int>> q;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
d[i][j] = -1;
if (a[i][j] == 1) {
q.push(make_pair(i,j));
d[i][j] = 0;
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
g[nx][ny] = g[x][y];
q.push(make_pair(nx,ny));
}
}
}
}
int ans = -1;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
for (int k=0; k<4; k++) {
int x = i+dx[k];
int y = j+dy[k];
if (0 <= x && x < n && 0 <= y && y < n) {
if (g[i][j] != g[x][y]) {
if (ans == -1 || ans > d[i][j] + d[x][y]) {
ans = d[i][j] + d[x][y];
}
}
}
}
}
}
printf("%d\n",ans);
return 0;
}'Problem set' 카테고리의 다른 글
| [백준] 13913 숨바꼭질 4 (0) | 2021.02.20 |
|---|---|
| [백준] 1697 숨바꼭질 (0) | 2021.02.20 |
| [백준] 16964 DFS 스페셜 저지 (0) | 2021.02.20 |
| [백준] 16940 BFS 스페셜 저지 (0) | 2021.02.20 |
| [백준] 7562 나이트의 이동 (0) | 2021.02.20 |