[Python] BOJ / 17472번 / 다리 만들기 2

17472번: 다리 만들기 2

 

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

 

 

 

다음은 올바르지 않은 3가지 방법이다

 

 

 

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

 

 

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

풀이

우선 가장 먼저 인접한 땅의 경우는 동일한 섬으로 취급하기 위해 BFS를 통해 새로 번호를 매겨주어야 합니다. 동시에 섬의 위치를 따로 저장해놓고 이를 통해 다리를 만들어야 합니다.

 

다리는 문제에 제시된 바와 같이 가로 또는 세로로 한쪽 방향으로만 이동해야하므로 BFS를 살짝 변형하여 구현해야하며 길이가 2이상인 다리의 경우만 고려해야합니다.

 

이후에는 위에서 생성한 다리들의 정보를 통해 크루스칼(Kruskal) 알고리즘을 수행하여 모든 섬들을 연결했을 때의 다리 길이의 최솟값을 구하면 됩니다.

 

보다 자세한 설명은 주석을 통해 달아놓도록 하겠습니다.

---

import sys
from collections import deque

input = sys.stdin.readline
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

def _numbering(i, j, num, visited):
    que = deque()
    que.append([i, j])

    while que:
        y, x = que.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if not 0 <= ny < n or not 0 <= nx < m: continue

            if country[ny][nx] and not visited[ny][nx]:
                country[ny][nx] = num
                visited[ny][nx] = True
                island_spot.append([ny, nx, num])
                que.append([ny, nx])

# 각 섬마다 서로 다른 번호를 부여하기 위함
def numbering():
    visited = [[0] * m for _ in range(n)]

    num = 1
    for i in range(n):
        for j in range(m):
            if country[i][j] and not visited[i][j]:
                visited[i][j] = True
                country[i][j] = num

                # 섬이 있는 위치와 번호 저장(이후 다리를 만들어 섬을 연결할 때 다리의 시작점이 됨)
                island_spot.append([i, j, num])

                _numbering(i, j, num, visited)
                num += 1
    
    return num - 1

# 섬을 연결하는 다리 만들기
def make_bridge(y, x, c):
    que = deque()

    # 한쪽 방향으로만 이동하는 BFS
    for i in range(4):
        que.append([y, x])
        visited = [[0] * m for _ in range(n)]
        temp = [[0] * m for _ in range(n)]  # 다리의 길이를 저장하기 위함
        visited[y][x] = True

        while que:
            yy, xx = que.popleft()
            ny = yy + dy[i]
            nx = xx + dx[i]

            if not 0 <= ny < n or not 0 <= nx < m: continue

            if not visited[ny][nx]:
                if country[ny][nx] == 0:    # 다음 위치가 바다인 경우 다리 생성
                    temp[ny][nx] = temp[yy][xx] + 1
                    que.append([ny, nx])

                # 다음 위치가 바다가 아니며(위 조건에 의해 걸러짐) 다리의 시작점 섬이 아니고, 다리의 길이가 2이상인 경우
                elif country[ny][nx] != c and temp[yy][xx] >= 2:
                    # 문제에 제시된 다리 연결 조건을 만족하므로 이후 크루스칼 알고리즘을 위해 사용할 bridges 배열에 추가
                    # [다리의 길이, 시작섬, 도착섬]
                    bridges.append([temp[yy][xx], c, country[ny][nx]])

# 크루스칼 알고리즘
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)

    if a != b:
        parent[a] = b

def kruskal():
    ans, cnt = 0, 0

    for dist, a, b in bridges:
        if find_parent(a) != find_parent(b):
            union_parent(a, b)
            ans += dist
            cnt += 1
            if cnt == num - 1: break

    return ans, cnt

n, m = map(int, input().split())
country = [list(map(int, input().split())) for _ in range(n)]
island_spot = []
bridges = []

num = numbering()

for y, x, c in island_spot: # 섬의 위치를 기준으로 다리 생성
    make_bridge(y, x, c)

parent = [i for i in range(num + 1)]
bridges.sort()  # 다리의 길이를 기준으로 오름차순 정렬

ans, cnt = kruskal()

if cnt == num - 1:  # 모든 섬을 연결했을 경우 즉, 다리 연결 횟수 = 섬의 개수 - 1
    print(ans)
else: print(-1)