BOJ 2146 · 다리 만들기

알고리즘 분류 : DFS, BFS  

섬과 섬 사이에 다리를 놓고, 가장 짧은 다리의 길이를 구하는 문제다. 땅을 DFS를 통해 하나의 섬으로 묶고, 각 섬과 섬 사이의 거리를 BFS를 통해 구하면 된다.

• 먼저 입력받은 맵에서 붙어있는 육지(1)를 찾아서 섬으로 묶어야 한다.
• 육지를 섬으로 그룹화하는 과정은 DFS를 통해 진행한다. 인접한 육지를 이동하면서 방문 체크를 하고, 카운트를 매긴다. 예를 들어, 첫 번째 섬은 1, 두 번째 섬은 2, ‥, N 번째 섬은 N으로 맵에 마킹한다.
• 섬을 체크했다면, 섬과 섬 사이를 BFS를 통해 이동한다.
• 바다(0)를 이동하다가, 출발한 섬과 다른 섬을 만나면, 이동거리를 최솟값으로 업데이트한다.

---

C++ 소스코드

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

struct bridge {
    int x, y;
};

int n, k=1, ans=1e9;
int a[101][101], dist[101][101];
bool check[101][101];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    check[x][y] = true;
    a[x][y] = k;
    for (int i=0; i<4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (!check[nx][ny] && a[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

void bfs(int z) {
    queue<bridge> q;
    memset(dist, -1, sizeof(dist));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j] == z) {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
       int x = q.front().x, y = q.front().y; q.pop();
       for (int i=0; i<4; i++) {
           int nx = x+dx[i], ny = y+dy[i];
           if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
           if (a[nx][ny] && a[nx][ny] != z) {
               if (ans > dist[x][y]) ans = dist[x][y];
               return;
           }
           if (!a[nx][ny] && dist[nx][ny] == -1) {
               dist[nx][ny] = dist[x][y]+1;
               q.push({nx, ny});
           }
       }
   }
}

void solve() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (!check[i][j] && a[i][j]) {
                dfs(i, j);
                k += 1;
            }
        }
    }
    for (int i=1; i<=k; i++) {
        bfs(i);
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    solve();
    return 0;
}

✓ 이전 코드가 틀린 코드여서, 업데이트하였음. (2019. 04. 30.)

---

Python 3 소스코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
check = [[False]*n for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, -1, 0, 1)
ans, k = 10**9, 1

def dfs(x, y):
    check[x][y] = True
    a[x][y] = k
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        if not check[nx][ny] and a[nx][ny]:
            dfs(nx, ny)

def bfs(z):
    global ans
    dist = [[-1]*n for _ in range(n)]
    q = deque()
    for i in range(n):
        for j in range(n):
            if a[i][j] == z:
                q.append((i, j))
                dist[i][j] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if a[nx][ny] and a[nx][ny] != z:
                ans = min(ans, dist[x][y])
                return
            if not a[nx][ny] and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y]+1
                q.append((nx, ny))

for i in range(n):
    for j in range(n):
        if not check[i][j] and a[i][j]:
            dfs(i, j)
            k += 1
for i in range(1, k+1):
    bfs(i)
print(ans)

---

참고

• 백준 온라인 저지 : BOJ 2146