백준 2146번 다리 만들기 :: 마이구미

이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.

이 문제는 BFS DFS 활용 문제이다.

하단에 비슷한 문제들이 나열되어 있다.

DFS, BFS 관련 글.

http://mygumi.tistory.com/102

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다.
이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.
가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다.
다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,

위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

섬과의 가장 짧은 경로를 찾는 문제이다.

이 문제의 해결방법은 간척사업이라고 한다.

간척사업이란, 각 섬들이 1칸씩 확장하는 것을 말한다.

위와 같이 1, 2 ,3 섬이 있을 경우, 각 섬의 주변을 한칸씩 확장하는 것을 말한다.

본인은 간척사업에과 최단 경로에 유용한 BFS를 사용하겠다.

BFS를 통해 큐에 넣는 특성을 생각해보면 간척사업을 이해할 수 있다.

크게 4가지로 진행절차를 추려보겠다.

1. 탐색을 통해 각 섬의 번호를 지정해준다.

2. 간척사업을 위해 각 섬을 큐에 넣는다.

3. 간척사업 과정(BFS) 중 서로 다른 섬이 만날 때 경로 측정.

4. 측정된 경로 중 가장 짧은 경로 조사.

1번 과정은 BFS를 통해 쉽게 번호를 지정해줄 수 있다.

같은 섬인 조건은 상하좌우가 연결되어있으면 된다.

조건문을 상하좌우 4개 만들 필요없이 아래와 같이 활용하자.

int[] dx = { 0, 0, 1, -1 };
int[] dy = { 1, -1, 0, 0 };

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

    if (0 < nx && nx <= n && 0 < ny && ny <= n) {

        if (a[ny][nx] == 1 && !c[ny][nx]) {
            q.add(new Pair(nx, ny));
            a[ny][nx] = idx;

            c[ny][nx] = true;
        }
    }
}

2번 과정은 번호가 지정된 섬들을 큐에 저장한다.

그 후 3번 과정인 BFS를 통해 간척사업을 진행하면서 간척사업의 길이를 저장하면서 서로 다른 섬이 만나는 지 체크를 한다.

for (int k = 0; k < 4; k++) {
    int nx = x + dx[k];
    int ny = y + dy[k];
    if (0 < nx && nx <= n && 0 < ny && ny <= n) {

        if (a[ny][nx] != 0 && a[ny][nx] != a[y][x]) {
            list.add(dist[ny][nx] + dist[y][x]);
        }

        if (a[ny][nx] == 0) {
            q.add(new Pair(nx, ny));

            a[ny][nx] = a[y][x];
            dist[ny][nx] = dist[y][x] + 1;
        }
    }
}

list에 저장된 경로 중 최단 경로를 찾으면 문제를 해결할 수 있다.

2146번 문제를 해결할 수 있다면 아래 문제들은 쉽게 풀 수 있다.

2146번 문제는 아래 문제들을 활용하여 해결할 수 있는 문제이기 때문이다.

Github URL을 통해 전체 소스를 확인하길바란다.

백준 알고리즘 문제 2146번 다리 만들기 - 토마토(7576번) + 섬의 개수(4963번) 응용

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

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/2146.java

백준 알고리즘 문제 7576번 토마토

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

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/7576.java

백준 알고리즘 문제 4963번 섬의 개수 - 단지번호 붙이기(2667번) 비슷

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

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/4963.java

백준 알고리즘 문제 2667번 단지번호붙이기 

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

https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/2667.java