백준 2146 다리 만들기

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

#define NSIZE 101
#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int N;
int input[NSIZE][NSIZE];
int v[NSIZE][NSIZE];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
    int y, x, cnt;
};
int Min = 0x7fffffff;
void init() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &input[i][j]);
        }
    }
}
queue<Data>q;
void dfs(int y, int x, int cnt) {
    for (int dir = 0; dir < 4; dir++) {
        int ny = y + dy[dir]; int nx = x + dx[dir];
        if (0 <= ny && ny < N && 0 <= nx && nx < N) {
            if (input[ny][nx] == 1) {
                input[ny][nx] = cnt;
                q.push({ ny,nx,0 });
                dfs(ny, nx, cnt);
            }
        }
    }
}
void islandSearch()
{
    int cnt = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (input[i][j] == 1) {
                while (!q.empty())q.pop();
                q.push({ i,j,0 });
                cnt++;
                input[i][j] = cnt;
                dfs(i, j, cnt);
                memset(v, 0, sizeof(v));
                while (!q.empty()) {
                    Data c = q.front(); q.pop();
                    if (input[c.y][c.x] != 0 && input[c.y][c.x] != cnt) {
                        if (Min > c.cnt - 1)Min = c.cnt - 1;
                        break;
                    }
                    for (int dir = 0; dir < 4; dir++) {
                        Data n;
                        n.y = c.y + dy[dir]; n.x = c.x + dx[dir];
                        n.cnt = c.cnt;
                        if (0 <= n.y && n.y < N && 0 <= n.x && n.x < N) {
                            if (v[n.y][n.x] == 0 && input[n.y][n.x] != cnt) {
                                v[n.y][n.x] = c.cnt + 1;
                                q.push({ n.y,n.x,n.cnt + 1 });
                            }
                        }
                    }
                }
            }
        }
    }
}
int main(void) {
    init();
    islandSearch();
    printf("%d\n", Min);
    return 0;
}

이문제는 dfs와 bfs가 가미된 문제인데 포인트는 우선 섬을 찾고 그섬을 큐에 전부 담은후

그섬에서 큐를 돌리면서 제일먼저 섬에 도달했을때의 cnt값 즉 최단거리의 최소를 출력하면됩니다.

무슨 말인지는 그림으로 보여드리겠습니다.

 

대신 cnt 는 cnt-1 이겠죠 다리의 길이이므로 그것은 소스를 참고해주시면 됩니다.

엄청 긴 소스는 아니니 쉽게 구현 가능하십니다. 

오늘은 여기까지이고 이런문제도 정말 풀면 기분 좋은데 못풀면 화나는 문제 이긴 하네요.