[백준] 17472번 - 다리 만들기 2

문제 분석

문제에서 주어진 N과 M의 크기가 매우 작은 편이라 시간 복잡도에 제약은 크지 않다.
문제를 해결하기 위해서는 먼저 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현하는 과정이 필요하다.
이후에는 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인하고 우선순위큐에 해당 거리를 기준으로 오름차순하여 에지 리스트의 형태로 저장한다.
마지막으로는 유니온파인드와 연결하여, 최소신장트리를 활용해 문제를 해결할 수 있다.
이때 최소신장트리에서는 에지의 개수는 '노드-1' 이 될때 까지 반복한다. (에지의 개수 == 노드 -1 이 되면 종료된다.)

소스 코드

# 다리 만들기

import sys
from queue import PriorityQueue
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[0 for j in range(M)] for i in range(N)]
queue = PriorityQueue()
edgeNum = 0
landNum = 2

for i in range(N):
    arr[i] = list(map(int, input().split()))


def makeLand(r, c, num):
    if (r >= 0 and r < N) and (c >= 0 and c < M) and (arr[r][c] == 1):
        arr[r][c] = num
        makeLand(r, c-1, num)
        makeLand(r-1, c, num)
        makeLand(r, c+1, num)
        makeLand(r+1, c, num)


for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            makeLand(i, j, landNum)
            landNum += 1

D = [0] * (landNum)
for i in range(2, len(D)):
    D[i] = i


def find(idx):
    if idx == D[idx]:
        return idx
    else:
        D[idx] = find(D[idx])
        return D[idx]


for i in range(N):
    for j in range(M):
        if arr[i][j] != 0:
            for end in range(j - 1, -1, -1):
                if arr[i][end] == arr[i][j]:
                    break
                if arr[i][end] != 0:
                    if j-end-1 >= 2:
                        queue.put((j-end-1, arr[i][j], arr[i][end]))
                    break
            for end in range(j+1, M):
                if arr[i][end] == arr[i][j]:
                    break
                if arr[i][end] != 0:
                    if end-j-1 >= 2:
                        queue.put((end-j-1, arr[i][j], arr[i][end]))
                    break
            for end in range(i-1, -1, -1):
                if arr[end][j] == arr[i][j]:
                    break
                if arr[end][j] != 0:
                    if i-end-1 >= 2:
                        queue.put((i-end-1, arr[i][j], arr[end][j]))
                    break
            for end in range(i+1, N):
                if arr[end][j] == arr[i][j]:
                    break
                if arr[end][j] != 0:
                    if end-i-1 >= 2:
                        queue.put((end-i-1, arr[i][j], arr[end][j]))
                    break

success = True
total = 0

while edgeNum < landNum - 2 - 1:
    if queue.empty():
        success = False
        break
    w, s, e = queue.get()
    if find(s) != find(e):
        edgeNum += 1
        total += w
        D[find(s)] = D[find(e)]


if not success:
    print(-1)
else:
    print(total)