[🥇2 / 백준 17472 / 파이썬] 다리 만들기 2

 

17472번: 다리 만들기 2

 

문제

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

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

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

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

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

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

 

다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

 

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

 

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

 

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

 

A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12

 

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

 

입력

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

출력

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

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

 

예제 입력 1 7 8 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	예제 출력 1  9
예제 입력 2  7 8 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	예제 출력 2  10
예제 입력 3  7 8 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0	예제 출력 3  9
예제 입력 4  7 7 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1	예제 출력 4  -1

 

풀이

 

고려해야 할 것이 엄청 많은 문제이다.

어려운 문제라기 보다는 할 것이 많아 번거로운 문제라고 할 수 있다.

 

크게 순서를 나누면 다음과 같다.

 

1. 섬의 영역별로 좌표 구하기
2. 다리 제작
3. 최소 스패닝 트리 수행

 

 

우선 섬의 어느 부분을 짚어서 다른 섬과 연결해야 할 지 알 수 없다.

따라서 지도를 순환하며 섬의 좌표를 그 섬의 영역별 번호와 함께 딕셔너리와 배열에 담을 것이다.

배열에 담는 이유는 후에 간선을 제작하기 위함이고, 딕셔너리는 해당 좌표를 빠르게 검색하여 해당 좌표의 부분이 어느 섬의 부분인지 알기 위함이다.

필자는 BFS로 해결했지만, DFS로 해도 무방하다.

 

 

이제 좌표를 구했으니 다리를 제작해야 한다.

문제에도 있지만, 주의해야 할 점을 정리하자면 아래와 같다.

 

1. 다리에 육지가 있어서는 안 된다.
2. 다리의 길이가 2보다 짧으면 안된다.
3. 다리는 직선이어야 한다.
4. 다리의 양 끝점에 육지가 존재해야 한다.

 

생각보다 많은데, 필자는 아까 구했던 좌표를 순환하며 상하좌우로 다리를 쭉 뻗는 방식으로 했다.

만약 다리를 뻗다가 섬 자기 자신과 만나거나, 지도 밖으로 벗어나면 다음 다리를 제작한다.

만약 위 모든 조건이 충족되었다면, 간선 리스트에 다리의 길이와, 두 섬의 번호를 튜플로 묶어서 넣는다.

 

 

다리 제작이 끝났다면 최소 스패닝 트리 알고리즘을 진행해야 한다.

필자는 프림과 크루스칼 중 크루스칼로 해결했다.

 

섬의 위치가 적절하지 않았을 경우, 다리의 개수가 부족하거나 스패닝 트리를 완성할 수 없을 수도 있다.

이 경우 -1을 출력한다.

 

from collections import deque
import sys, heapq
input = sys.stdin.readline

n,m = map(int,input().split())
board = [list(map(int,input().split())) for _ in range(n)]
visit = [[False]*m for _ in range(n)]
move = [(0,1),(1,0),(0,-1),(-1,0)]
land = dict()
landArr = []

# 섬 구분하여 좌표 구하기, BFS
landNum = 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 1 and not visit[i][j]:
            q = deque([(i,j)])
            visit[i][j] = True
            land[(i,j)] = landNum
            landArr.append((i,j,landNum))
            while q:
                x,y = q.popleft()
                for a,b in move:
                    dx=x+a; dy=y+b
                    if n>dx>=0 and m>dy>=0 and not visit[dx][dy] and board[dx][dy]:
                        q.append((dx,dy))
                        visit[dx][dy] = True
                        land[(dx,dy)] = landNum
                        landArr.append((dx,dy,landNum))
            landNum += 1

# 다리 제작
edges = []
for x,y,curLand in landArr:
    for a,b in move:
        dist = 0
        dx=x+a; dy=y+b
        while True:
            if n>dx>=0 and m>dy>=0:
                toLand = land.get((dx,dy))
                # 같은 섬
                if curLand==toLand:
                    break
                # 바다 위, 다리 길이 +1
                if toLand == None:
                    dx+=a; dy+=b
                    dist+=1
                    continue
                # 다리가 짧음
                if dist < 2:
                    break
                edges.append((dist,curLand,toLand))
                break
            else:
                break
edges = sorted(edges,reverse=True)

# 크루스칼 진행
def union(x,y):
    x = find(x)
    y = find(y)
    parents[y] = x

def find(k):
    if k != parents[k]:
        parents[k] = find(parents[k])
    return parents[k]

ans = 0
cnt = landNum-1
parents = [i for i in range(landNum)]
while cnt:
    try:
        w,a,b = edges.pop()
    except:
        # empty list, 다리 부족
        print(-1)
        sys.exit()
    if find(a) != find(b):
        union(a,b)
        ans += w
        cnt-=1
print(ans)