백준 17472번: 다리 만들기 2 (Python)

접근

결론적으로는 최소 신장 트리, MST 알고리즘을 이용하여 푸는 문제가 맞지만, 그 전에 그 다리들을 처리하는 것이 굉장히 까다롭게 느껴졌던 문제이다. 단계별을 풀면서 MST 알고리즘을 몇가지 풀어봤으면, 이 문제는 MST 알고리즘을 적용하는 것이 아닌 그 전에 처리하는 것이 어려웠던 문제였던 것 같다.

MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python)

백준 1197번: 최소 스패닝 트리 (Python)

문제해결 1단계: 섬 라벨링

이 문제를 풀면서 가장 먼저 했던 것은 각 섬들을 라벨링하는 것이다. BFS 알고리즘을 이용하여 연결된 섬들을 탐색하고, 같이 연결되어있는 땅끼리 같은 숫자로 라벨링 해주는 과정이다. 처음에 주어진 지도에서 땅을 1로 표시하였기 때문에 2번부터 라벨링해주었다. 즉 내 코드에서는 2번 섬이 첫번째 섬이고, 섬들을 탐색할 때 2번 섬부터 탐색하게 된다. 그 과정에서 섬들의 외곽 좌표들을 저장해주어 다리 시작점을 순환할 때 사용하기로 한다. (코드 참고)

문제해결 2단계: 각 섬을 연결하는 다리 찾기

위에서 구했던 섬들의 외곽 좌표에서 한 방향으로 진행하며 다른 섬을 만날 때까지 다리의 길이를 저장한다. 이때 다리 길이가 2보다 크다면(문제의 조건) bridges 리스트를 갱신해준다.(코드 참고) 지도에서 만들 수 있는 모든 다리들을 찾아 갱신해주었으면 이 리스트를 [다리의 길이, 다리의 시작 섬, 다리의 도착 섬] 의 형태로 저장해주고, 이제 이 자료를 가지고 보통의 유니온파인드 방법으로 각 섬들을 연결해주면 된다.

코드에도 주석으로 설명을 달아놓았으니 확인하면 좋을 것이다.

코드

import sys


def ismap(x, y):  # 해당 좌표가 지도 안에 있는지 판단해주는 함수
    if 0 <= x < n and 0 <= y < m:
        return True
    else:
        return False


n, m = map(int, sys.stdin.readline().split())
mapArr = []  # 지도 Array
for _ in range(n):
    mapArr.append(list(map(int, sys.stdin.readline().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
boundary = [[] for _ in range(8)]  # boundary[i]: i 섬의 외곽 좌표, 다리의 시작점 탐색 때 사용


def labeling(x, label):  # mapArr x 좌표에서 시작하여 연결된 땅들을 label 숫자로 바꾸어주는 함수
    q = [x]
    mapArr[x[0]][x[1]] = label
    tmpBoundary = []  # label 되고 있는 섬의 외곽 좌표들을 저장해주는 임시 list
    while q:
        now = q.pop(0)
        boundaryCheck = False
        for k in range(4):
            nx, ny = now[0] + dx[k], now[1] + dy[k]
            if ismap(nx, ny):
                if mapArr[nx][ny] == 1:
                    mapArr[nx][ny] = label
                    q.append([nx, ny])
                elif mapArr[nx][ny] == 0:  # now 좌표를 기준으로 주변에 0, 즉 바다가 있으면 외곽 좌표 표시
                    boundaryCheck = True
        if boundaryCheck:
            tmpBoundary.append([now[0], now[1]])
    boundary[label] = tmpBoundary


label = 2  # 주어진 지도에 땅이 1로 표시되어 있으므로 섬을 2부터 라벨링
for i in range(n):
    for j in range(m):
        if mapArr[i][j] == 1:
            labeling([i, j], label)
            label += 1
# 이 과정 후에 label 은 마지막 라벨링된 섬이 가진 수 +1 의 값을 가짐
bridges = [[0] * label for _ in range(label)]  # bridges[i][j]: i 섬에서 j 섬까지 연결하는 다리의 길이

for now in range(2, label):  # 각 섬들을 탐색
    for x, y in boundary[now]:  # 각 섬들의 외곽 좌표를 탐색
        for k in range(4):  # 각 섬들의 외곽에서 4방향으로 탐색하여 지도 밖으로 나가거나, 다른 섬을 만날때까지 탐색
            nx, ny = x + dx[k], y + dy[k]
            if ismap(nx, ny):
                cnt = 0
                while mapArr[nx][ny] == 0:
                    cnt += 1
                    nx += dx[k]
                    ny += dy[k]
                    if not ismap(nx, ny):
                        cnt = 0
                        break
                if cnt >= 2:  # 다리가 진행하다가 다른 섬을 만났을 경우 해당 섬과의 bridges 리스트를 갱신
                    if bridges[now][mapArr[nx][ny]]:
                        bridges[now][mapArr[nx][ny]] = min(bridges[now][mapArr[nx][ny]], cnt)
                        bridges[mapArr[nx][ny]][now] = bridges[now][mapArr[nx][ny]]
                    else:
                        bridges[now][mapArr[nx][ny]] = cnt
                        bridges[mapArr[nx][ny]][now] = cnt

lines = []
for i in range(2, label):
    for j in range(i + 1, label):
        if bridges[i][j]:
            lines.append([bridges[i][j], i, j])  # i 에서 j 로 가는 다리의 길이가 bridges[i][j]
# 이 과정을 거친 후에는 보통의 유니온파인드 문제들과 같이 풀이
parent = [i for i in range(label)]
lines.sort()


def find(x):
    if parent[x] == x:
        return x
    p = find(parent[x])
    parent[x] = p
    return p


def union(x, y):
    parent[y] = x


cnt2 = 0
ans = 0
for co in lines:
    d, a, b = co
    ar = find(a)
    br = find(b)
    if ar != br:
        union(ar, br)
        ans += d
        cnt2 += 1
    if cnt2 == label - 3:
        break
if cnt2 != label - 3:  # 모든 다리들의 탐색이 끝났는데 다리의 수가 섬의 개수 - 1 개가 되지 않으면
    print(-1)  # 연결되지 않은 섬이 존재
else:
    print(ans)  # 그렇지 않으면 다리의 총 길이 출력

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!