백준 2146 - 다리 만들기

백준 2146 문제 바로가기

유사한 문제로 ‘백준 17472 - 다리 만들기 2’가 있다. ‘다리 만들기’ 문제는 ‘다리 만들기 2’ 문제의 EASY 버전이라고 생각하면 될 것 같다. (‘다리 만들기’ 문제에서는 MST 개념이 필요하지 않고, 다리를 일직선으로만 놓지 않아도 된다.)

풀이

문제 설명

0과 1로 이루어진 NxN 지도가 주어진다. (0 : 바다, 1 : 육지)

바다에 다리를 놓아 두 대륙을 연결시킬 때, 가장 짧은 다리의 길이를 구한다. (대륙이 여러개 있어도, 두 대륙을 연결시킬 수 있는 가장 짧은 다리의 길이만 구하면 된다.)

가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다.

---

우선 두 대륙을 판별하기 위해서는 육지를 식별할 수 있도록 넘버링이 되어있어야 한다. (예를 들어 육지가 ㄷ자 모양으로 구성되어 있고 바다에 다리를 놓으면서 육지에 도달했을 때, 도달한 육지가 출발점 육지와 동일한지 판별하기가 난해하다.)

1. 육지에 번호 매기기

2중 for문을 돌면서 바다가 아닌 위치를 시작점으로 잡고, 4방향(상하좌우)에 대해 중복방문을 허용하지 않으면서 DFS를 수행한다. number[r][c] = num 문장에 의해 4방향으로 인접한 육지에 대해서 동일한 번호를 매긴다.

2. 모든 육지의 위치(r, c)에서 다리를 놓아보며, 다리의 최소 길이 구하기

최소 길이를 구하려면 한 시점에서 이동할 수 있는 모든 방향에 대해 이동을 해야하므로 BFS를 수행한다. 육지의 시작점(r, c)의 육지 번호(number[r][c])와 다른 육지 번호를 갖는 섬이 나올 때까지 반복한다.

실행 시간 단축 목적으로 visited[r][c] 배열을 일일이 초기화하는 것을 방지하기 위해 정수 배열로 선언하고 중복 방문 회피를 위해 bfsNum 값을 사용했다. bfsNum 값은 bfs 함수가 호출될 때마다 1씩 증가하며 visited[r][c] == bfsNum 식이 true인 경우에는 이미 방문한 위치임을 의미한다.

• m[nr][nc] == 0인 경우에는 이동하려는 위치가 바다이므로, 큐에 다음 위치의 정보 pos(nr, nc, now.dist + 1)를 저장한다.

• number[r][c] != number[nr][nc]인 경우에는 시작 위치의 섬 번호와 현재 도달한 섬 번호가 다르다는 것은 다리를 놓아서 다른 섬을 잇게 되었다는 의미이므로, 이때의 now.dist 값이 최솟값이라면 ans에 갱신한다. 이때, m[nr][nc]는 바다가 아니라 섬이므로 최솟값을 갱신할 때 now.dist + 1이 아님에 유의한다.

소스 코드

// C++14
#include <iostream>
#include <queue>
using namespace std;

struct pos {
    int r;
    int c;
    int dist;
    pos(int r, int c, int dist) : r(r), c(c), dist(dist) {}
};
int N;
int m[100][100];
int ans;

const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };

// numbering
int num;
int number[100][100];
void numbering(int r, int c) {
    number[r][c] = num;
    for (int d = 0; d != 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
        if (m[nr][nc] == 0 || number[nr][nc] == num) continue;
        numbering(nr, nc);
    }
}

int visited[100][100];
int bfsNum;
void bfs(const int r, const int c) {
    ++bfsNum;
    visited[r][c] = bfsNum;
    queue<pos> q;
    q.push({ r,c,0 });
    while (!q.empty()) {
        const pos now = q.front();
        q.pop();
        for (int d = 0; d != 4; ++d) {
            int nr = now.r + dr[d];
            int nc = now.c + dc[d];
            if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
            if (number[r][c] == number[nr][nc]) continue; // 똑같은 섬
            if (visited[nr][nc] == bfsNum) continue; // 방문한 곳

            visited[nr][nc] = bfsNum;

            // 바다
            if (m[nr][nc] == 0) {
                q.push(std::move(pos(nr, nc, now.dist + 1)));
            }
            else if (number[r][c] != number[nr][nc]) {
                if (ans > now.dist) {
                    ans = now.dist;
                }
                return;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            cin >> m[r][c];
        }
    }

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (m[r][c] == 1 && number[r][c] == 0) {
                ++num;
                numbering(r, c);
            }
        }
    }

    ans = ~(1 << 31);

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            if (number[r][c] != 0) {
                bfs(r, c);
            }
        }
    }

    cout << ans;
    return 0;
}