17472: 다리 만들기 2

문제이해

문제가 호흡이 긴데 요약하자면 1로 된 섬과 0으로 된 바다로 이루어진 매트릭스가 주어질 때 최소 비용으로 그 섬을 모두 연결하는 문제이다. 다만, 다리는 직선이어야 하고 길이가 2 이상 이어야 한다.

계획

일단 이문제의 핵심은 모든 섬을 최소비용으로 연결해야 한다는 점이다. 이 점만 본다면 일반 최소신장트리(MST) 문제와 다르지 않다. 크루스칼을 쓰면서 섬을 추가하면 된다. 다만 그러기 위해서는 각 섬과의 다리 개수와 길이, 섬의 개수가 필요하다. 따라서, 첫 번째로 주어지는 매트릭스에서 그러한 정보를 추출해야 한다. 이 문제의 대략적인 순서는 아래와 같아야 한다.

1. 매트릭스에서 섬위치와 개수 파악

2. 매트릭스에서 다리 개수와 길이 추출

3. 크루스칼

먼저 매트릭스에서 섬이 같은 섬인지 다른 섬인지부터 구분을 해야 한다. 

0101

1101

1001

1111

위와 같은 모양의 섬도 인식할 수 있어야 하므로 매트릭스를 (0,0)부터 순서대로 순회하며 1을 마주칠 때마다 dfs로 섬을 탐색하게 했다. 그리고 나중에 다리 길이를 파악해야 하므로 1을 섬의 번호로 바꿔준다.

0100        0100

0001  ->  0002

0100        0300

그다음은 다리 길이와 개수를 구해줘야 한다. 일단 모든 섬을 최단거리로 이동할 수 있어야 하므로 각 섬을 잇는 다리길이 중 2 이상이지만 가장 짧은 다리의 길이와 잇는 섬을 기록한 배열을 만들어준다.

마지막으로, 그 배열을 이용해 크루스칼을 이용하면 문제를 해결할 수 있다.

 

 

계획수행

import sys, heapq
sys.setrecursionlimit(100000)

n, m = map(int, sys.stdin.readline().split())
map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]

#같은 섬 파악하는 함수
def findIsland(r, c, v):
    visited[r][c] = True
    map[r][c] = v
    nr = [r, r, r-1, r+1]
    nc = [c-1, c+1, c, c]
    for i in range(4):
        n1 = nr[i]
        n2 = nc[i]
        if 0 <= n1 < n and 0 <= n2 < m and not visited[n1][n2] and map[n1][n2] != 0:
            findIsland(n1, n2, v)

#해당 섬의 트리의 루트를 파악하는 함수
def find(t):
    if p[t] == t:
        return t
    p[t] = find(p[t])
    return p[t]

#a와 b가 같은 트리인지 파악하는 함수
def union(a, b):
    a, b = find(a), find(b)
    if a == b:
        return True
    if a > b:
        p[a] = b
    else:
        p[b] = a
    return False

cnt = 1    #섬 개수 + 1
for i in range(n):
    for ii in range(m):
        if not visited[i][ii] and map[i][ii] == 1:
            findIsland(i, ii, cnt)
            cnt += 1

#만약 섬이 한개면 연결될 필요 없음.
if cnt == 2:
    print(0)
    exit(0)

p = [i for i in range(cnt)]
bridge = [[11 for _ in range(cnt)] for _ in range(cnt)]
#가로 다리 파악
for i in range(n):
    pl, dist = 0, 0
    for ii in range(m):
        #만약 이전이 섬이고 현재가 바다일때 다리 시작
        if 0 < ii and map[i][ii] == 0 and map[i][ii-1] != 0:
            pl = map[i][ii-1]
            dist += 1
        #이미 다리가 시작 됐고, 현재가 바다라면 다리 연장
        elif dist != 0 and map[i][ii] == 0:
            dist += 1
        #만약 다리가 시작 됐는데 육지 발견했을때
        elif dist != 0 and map[i][ii] != 0:
            #만약 1이 아니라면 다리 길이와 잇고있는 섬 저장
            if dist != 1:
                bridge[map[i][ii]][pl] = min(bridge[map[i][ii]][pl], dist)
                bridge[pl][map[i][ii]] = min(bridge[pl][map[i][ii]], dist)
            pl, dist = 0, 0

#세로 다리 파악(가로 다리 파악과 동일)
for i in range(m):
    pl, dist = 0, 0
    for ii in range(n):
        if 0 < ii and map[ii][i] == 0 and map[ii-1][i] != 0:
            pl = map[ii-1][i]
            dist += 1
        elif dist != 0 and map[ii][i] == 0:
            dist += 1
        elif dist != 0 and map[ii][i] != 0:
            if dist != 1:
                bridge[map[ii][i]][pl] = min(bridge[map[ii][i]][pl], dist)
                bridge[pl][map[ii][i]] = min(bridge[pl][map[ii][i]], dist)
            pl, dist = 0, 0

line = []
#다리 길이와 종류 길이가 짧은 순으로 line에 저장
for i in range(cnt):
    for ii in range(i):
        if bridge[i][ii] != 11:
            heapq.heappush(line, (bridge[i][ii], i, ii))

#일반적인 MST문제
ans = 0
while line:
    dist, x1, x2 = heapq.heappop(line)
    if not union(x1, x2):
        ans += dist

#모든 섬이 연결돼 있는지 확인
for i in range(1, cnt):
    for ii in range(1, i):
        if not union(i, ii):
            print(-1)
            exit(0)

print(ans)

 

느낀 점

처음에 문제가 길어서 졸았는데 그냥 하나하나 구해야 하는 거 확인하면 쉬웠던 문제다.