[백준] 2146 다리 만들기

2146번: 다리 만들기

 

www.acmicpc.net

풀이

까다로운 BFS 문제이다. 2번의 BFS를 통해 해결하였다.

1. 섬들의 번호를 매긴다.
2. 섬들의 거리를 구한다.

섬들의 번호를 매기는 경우는 한 육지에서 인접한 육지를 계속해서 탐색함으로써 쉽게 해결할 수 있다.

섬들 간의 거리를 구하는 것은 한 육지에서 인접한 바다를 탐색하며 다른 번호의 육지가 나올 때까지 탐색하면 된다.

코드

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int n, ans = 987654321;
int map[101][101];
bool visited[101][101];
vector<pair<int, int>> p;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void divide_field(int x, int y, int idx) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    map[y][x] = idx;
    visited[y][x] = true;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            // 범위를 벗어나는 경우
            if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
            // 아직 섬을 탐색하지 않은 경우
            if (map[ny][nx] == -1 && !visited[ny][nx]) {
                // 섬의 번호를 매긴다
                map[ny][nx] = idx;
                visited[ny][nx] = true;
                q.push({ nx, ny });
            }
        }
    }
}

int make_bridge(int idx) {
    memset(visited, 0, sizeof(visited));
    queue<pair<pair<int, int>, int>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == idx) {
                visited[i][j] = true;
                q.push({ {j, i}, 0 });
            }
        }
    }

    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int cnt = q.front().second;
            // 이미 계산된 값보다 크면 종료시키는 방식으로 가지치기를 한다.
            if (ans < cnt) return 987654321;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
                // 바다도 아니고 현재 섬도 아닌 경우는 다른 섬과 연결된 것이므로 리턴해준다
                if (map[ny][nx] != 0 && map[ny][nx] != idx) return cnt;
                // 아직 방문하지 않은 바다의 경우 계속해서 탐색한다
                if (map[ny][nx] == 0 && visited[ny][nx] == 0) {
                    q.push({ {nx, ny}, cnt + 1 });
                    visited[ny][nx] = true;
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            if (map[i][j]) {
                // 별도의 배열 생성 없이 섬의 번호를 매기기 위해서 -1로 변경해준다.
                map[i][j] = -1;
                // 땅을 벡터에 미리 저장해둔다
                p.push_back({ j, i });
            }
        }

    int idx = 1;
    for (int i = 0; i < p.size(); i++) {
        int x = p[i].first;
        int y = p[i].second;
        if (!visited[y][x]) divide_field(x, y, idx++);
    }

    for (int i = 1; i < idx; i++) 
        ans = min(ans, make_bridge(i));
    cout << ans << '\n';
    return 0;
}