[백준 17472] 다리 만들기 2(Python)

1. 아이디어

우선 가장 먼저 해야할 일이 섬들에게 번호를 부여하는 것이다. 인접한 땅은 동일한 섬에 소속되어야 한다. 이를 구현하기 위해 BFS를 사용한다.

다음으로 해야할 일은 섬들을 연결하는 다리를 만드는 것이다. 여기서 주의해야할 점은 섬을 연결할 때, 한 방향으로만 다리를 만들어나가야한다. 또한, 다리의 길이가 2이상이여야한다. 참고로 다리가 교차하는 것을 허용한다. 한 방향으로 다리를 이어나가는 예시는 문제에 잘 설명되어있으니 참고하면된다. 한 방향으로만 가는 BFS를 구현한다. 구체적인 예시는 아래와 같다.

d = ((0,1), (0,-1), (1,0), (-1,0))
q = deque()
    
    for dy, dx in d:
        q.append((sy, sx))
        visited = [[False for _ in range(c)] for _ in range(r)]
        visited[sy][sx] = True
        table = [[0 for _ in range(c)] for _ in range(r)]

        while q:
            y, x = q.popleft()
            ny = y + dy
            nx = x + dx
            ...

다리 연결이 조건을 만족하면 다리에 연결된 섬번호와 다리의 길이를 리스트에 추가한다. 이후 MST로 해결하면된다. 주의해야할 점은 MST에서 선택된 다리의 개수가 섬 개수 - 1이 아니라면 모든 섬이 서로 연결되지 않는 것을 의미하므로 -1를 출력해야한다.

2. 코드

import sys
from collections import deque

r, c = map(int, sys.stdin.readline().rsplit())
islands = [[0 for _ in range(c)] for _ in range(r)]
arr = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(r)]
d = ((0,1), (0,-1), (1,0), (-1,0))
edges = []
cordis = []

def isin(y, x):
    if -1<y<r and -1<x<c: return True
    return False

def _make_islands(visited, sy, sx, k):
    q = deque()
    q.append((sy, sx))

    while q:
        y, x = q.popleft()
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if not isin(ny, nx): continue
            if not visited[ny][nx]:
                visited[ny][nx] = True
                if arr[ny][nx] == 1:
                    islands[ny][nx] = k
                    q.append((ny, nx))
                    cordis.append((ny, nx, k))

def make_islands():
    visited = [[False for _ in range(c)] for _ in range(r)]
    k = 1
    for i in range(r):
        for j in range(c):
            if not visited[i][j] and arr[i][j] == 1:
                visited[i][j] = True
                islands[i][j] = k
                cordis.append((i, j, k))
                _make_islands(visited, i, j, k)
                k += 1
    
    return k

def _find_routes(sy, sx, k):
    q = deque()
    
    for dy, dx in d:
        q.append((sy, sx))
        visited = [[False for _ in range(c)] for _ in range(r)]
        visited[sy][sx] = True
        table = [[0 for _ in range(c)] for _ in range(r)]

        while q:
            y, x = q.popleft()
            ny = y + dy
            nx = x + dx

            if not isin(ny, nx): continue
            if not visited[ny][nx]:
                visited[ny][nx] = True
                if islands[ny][nx] == 0:
                    table[ny][nx] = table[y][x] + 1
                    q.append((ny, nx))
                    
                elif islands[ny][nx] != k and table[y][x] >= 2:
                    edges.append((table[y][x], k, islands[ny][nx]))

def find_routes():
    for y, x, k in cordis:
        _find_routes(y, x, k)

n = make_islands() - 1
find_routes()
uf = [-1 for _ in range(n+1)]

def find(a):
    if uf[a] < 0: return a
    uf[a] = find(uf[a])
    return uf[a]

def merge(a, b):
    a = find(a)
    b = find(b)
    if a == b: return False
    uf[b] = a
    return True

edges.sort()
total, cnt = 0, 0

for w, a, b in edges:
    if merge(a, b):
        total += w
        cnt += 1
        if cnt == n-1: break
if cnt == n-1: print(total)
else: print(-1)