백준 17472 - 다리 만들기 2 (파이썬)

이번 문제는 개인적으로 굉장히 어려웠던 문제였습니다.
문제는 다음과 같은 순서로 해결했습니다.

1. bfs로 country배열을 돌면서 각각의 섬들에 고유번호를 붙여줍니다.
2. 1이 나오다가 0이 나오면 0이 나오기 바로 전의 좌표가 섬의 가장자리라 판단해 좌표와 방향을 edges배열에 넣어줍니다.
3. get_bridges함수를 호출해서 일정한 방향으로 더해가며 거리를 늘려가다가 0이 아닌 다른 섬의 번호가 나오면 bridges배열에 다리를 넣어줍니다.
4. bridges 배열을 거리순으로 정렬해 크루스칼 알고리즘을 사용합니다.

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
country = [list(map(int, input().split())) for _ in range(N)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
edges = []

def solve():
    global parent
    
    max_num = make_islands()
    parent = [i for i in range(max_num)]
    result = 0
    bridge_count = 0
    
    bridges = get_bridges()
    
    for cost, x, y in bridges:
        if find(x) != find(y):
            union(x, y)
            result += cost
            bridge_count += 1
            if bridge_count == max_num - 3:
                print(result)
                return
    
    print(-1)

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

def union(a, b):
    global parent
    
    a = find(a)
    b = find(b)
    
    if a != b:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

def get_bridges():
    bridges = set()
    
    for k, x, y in edges:
        start = country[x][y]
        cnt = 0
        while True:
            x += directions[k][0]
            y += directions[k][1]
            
            if 0 <= x < N and 0 <= y < M:
                end = country[x][y]
                
                if end != 0:
                    if start != end and cnt >= 2:
                        bridges.add((cnt, start, end))
                    break
                cnt += 1
            else:
                break
                
    return sorted(bridges)
            
def make_islands():
    number = 2
    for i in range(N):
        for j in range(M):
            if country[i][j] == 1:
                q = deque([(i, j)])
                while q:
                    x, y = q.popleft()
                    country[x][y] = number
                    for k in range(4):
                        dx = x + directions[k][0]
                        dy = y + directions[k][1]
                        
                        if 0 <= dx < N and 0 <= dy < M:
                            if country[dx][dy] == 1:
                                q.append((dx, dy))
                            elif country[dx][dy] == 0:
                                edges.append((k, x, y))
                number += 1
                
    return number

solve()