[BOJ] 2146. 다리 만들기

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

2146번: 다리 만들기

먼저 BFS탐색으로 각 섬에 번호를 붙여준다. 이와 관련된 비슷한 문제는 단지 번호 붙이기 문제를 (풀이) 풀어보면 된다. 

 

 

번호를 붙였으면 바다가 아닌 모든 칸에서 다른 섬으로 가는 최단 거리를 다시 BFS로 구한다.

한칸씩 이동할 때마다 거리를 늘려주기 위해서 큐 사이즈만큼씩 진행한다.

큐 사이즈가 한번 이동했을 때 갈 수 있는 칸들이기 때문이다.

 

BFS를 할때에는

이동할 칸이 현재와 같은 섬인 경우 (같은 번호인 경우)는 이동하지 않는다.

이동할 칸이 바다라면 이동한다.

이동할 칸이 다른 섬이라면 그때까지의 거리를 최소거리와 비교하여 더 작다면 갱신해준다.

 

 

모든 칸에서 가능한 최소거리를 구해야 하므로 BFS로 리턴 받은 최소거리들 중 다시 최소거리가 정답이다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
 
int n;
int map[100][100];
int island[100][100];
bool check[100][100];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
//섬에 번호를 붙인다
void bfs(int x, int y, int num) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    island[x][y] = num;
 
    while (!q.empty()) {
        x = q.front().first;
        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 (map[nx][ny] == 0) continue;
            //이미 번호를 붙인 경우
            if (island[nx][ny] != 0) continue;
 
            q.push(make_pair(nx, ny));
            island[nx][ny] = num;
        }
    }
}
 
 
//최소 거리를 계산한다.
int bfs2(int x, int y, int now) {
    memset(check, false, sizeof(check));
 
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int dist = 0;
    int mindist = 100000;
    while (!q.empty()) {
        int size = q.size();
 
        while (size--) {
            x = q.front().first;
            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 (island[nx][ny] == now) continue;
                //이미 방문한 경우
                if (check[nx][ny]) continue;
 
                //바다인 경우 일단 이동한다.
                if (island[nx][ny] == 0) {
                    q.push(make_pair(nx, ny));
                    check[nx][ny] = true;
                }
                else {
                    //바다도 아니고 현재 섬이 아닌 다른 섬이면 지금까지의 거리를 최소거리와 비교한다.
                    if (mindist > dist) mindist = dist;
                }
 
            }
        }
 
        //한번에 갈 수 있는 탐색이 끝나면 거리 증가
        dist++;
 
    }
 
    return mindist;
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    //연결된 섬들에 번호를 붙인다.
    int num = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //이미 번호가 붙은 경우
            if (island[i][j] != 0) continue;
            //바다인 경우
            if (map[i][j] == 0) continue;
 
            bfs(i, j, ++num);
        }
    }
 
 
    int ans = 100000;
    int tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //바다인 경우
            if (map[i][j] == 0) continue;
 
            //(i,j)에서 갈 수 있는 가장 가까운 다른 섬까지의 거리를 tmp에 저장
            tmp = bfs2(i, j, island[i][j]);
            //최솟값과 비교
            if (ans > tmp) ans = tmp;
        }
    }
 
    cout << ans << '\n';
 
 
    return 0;
}