BOJ 2146 다리 만들기 (DFS, BFS)

백준 BOJ 2146번 : 다리 만들기

Solved.ac 난이도 : Gold III

알고리즘 분류 : DFS, BFS

 

 

위의 그림과 같이 몇 개의 섬으로 이루어진 지도가 주어지면, 섬들 중 두 개를 잇는 가장 짧은 다리(그림에서 빨간색 칸에 해당)의 길이를 구하는 문제입니다.

 

우선 다리의 길이를 구하는 과정은 BFS로 구현해야함을 떠올릴 수 있습니다.

섬에 해당하는 칸 중에서, 이 칸과 인접한 바다에서부터 BFS를 시작하여 다른 섬에 해당하는 칸이 나올 때까지 반복하면 됩니다.

 

그런데 생각해보면, 같은 섬으로 돌아오는 것은 문제에서 정의한 '다리'에 해당하지 않으므로, 같은 섬을 구별할 수 있는 장치가 필요합니다.

따라서 탐색을 하기 전에 미리 같은 섬끼리 같은 숫자로 묶어서 표시를 해두어야 합니다.

그렇기 때문에 아래 코드의 coloring 함수와 같이 각 섬을 다른 숫자로 표기해줍니다.

 

그 다음에는 일반적인 BFS와 같습니다.

현재 섬의 번호와 다른 번호가 나타날 때까지 BFS를 해주고, 이 때의 길이를 최솟값으로 갱신해주면서 답을 찾아주면 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 101
using namespace std;

int N;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int arr[MAX][MAX], vis[MAX][MAX];

void clear_vis() {
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) vis[i][j] = 0;
}

int color = 2;
void coloring(int x, int y) {
    vis[x][y] = 1;
    arr[x][y] = color;

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(vis[nx][ny] == 0 && arr[nx][ny] == 1) coloring(nx, ny);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) cin >> arr[i][j];

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(arr[i][j] == 1) {
                clear_vis();
                coloring(i, j);
                color++;
            }

    int ans = INT_MAX;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(arr[i][j] != 0) {
                clear_vis();
                queue<pair<int, int>> q;
                int curr_color = arr[i][j];

                for(int k=0; k<4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                    if(arr[nx][ny] == 0) {
                        q.push({nx, ny});
                        vis[nx][ny] = 1;
                    }
                }

                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(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                        if(arr[nx][ny] != 0 && arr[nx][ny] != curr_color && vis[nx][ny] == 0) {
                            vis[nx][ny] = vis[x][y] + 1;
                            ans = min(ans, vis[x][y]);
                        }

                        if(arr[nx][ny] == 0 && vis[nx][ny] == 0) {
                            vis[nx][ny] = vis[x][y] + 1;
                            q.push({nx, ny});
                        }
                    }
                }
            }

    cout << ans;
}