[백준] 다리 만들기 2 (17472번) - Python / MST ( Kruskal Algorithm )

✅ 문제 - [백준] 다리 만들기 2 (17472번)

---

 

✅ 필요 알고리즘 개념 - BFS / MST ( Kruskal Alogorithm )

---

🎯 크루스칼 알고리즘( Kruskal Alghrithm ) 이란?

크루스칼 알고리즘이란, 그래프 자료구조에서 그리디 알고리즘을 적용해 MST ( Minimum Spanning Tree , 최소 신장 트리 )를 찾는 방법이다.

 

그리디 알고리즘의 경우 순간의 최선의 선택이 결과적으로 최선의 선택임을 증명해야 하는데

MST를 푸는 알고리즘 중 프림(Prim's) 알고리즘과 크루스칼(Kruskal) 알고리즘은 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다.

 

크루스칼 알고리즘을 적용하는 순서는 다음과 같다.

1. 간선을 리스트에 ( 길이, 노드1, 노드2 ) 형식으로 저장한다.
2. 간선을 저장한 리스트를 길이가 짧은 순으로 정렬한다.
3. 모든 간선을 탐색해 나가며 길이가 작은 값 부터 선택해 나가며 노드들을 연결해 나간다.
4. 연결하는 도 중 싸이클이 형성 되는 경우에는 그 노드는 연결하지 않고 지나간다
5. ( 이 때 싸이클 형성은 Union - Find 알고리즘을 이용하여 검출한다. )

 

✅ 문제 풀이 아이디어

---

코드가 길고 여러 함수가 나오므로

먼저 어떤 아이디어로 해결했는지, 아이디어를 먼저 알아보자.

 

1. 먼저 섬에 전부 다른 번호를 부여하여 섬들을 구분한다.

    ( 문제의 예시로 준 입력을 다음과 같이 2,3,4,5 번 섬으로 구분한다. )

이렇게 섬을 구분해 주는 이유는 뒤에 Union Find 알고리즘을 사용하기 위함이다.

 

2. 각 섬에서 다른 섬으로 이어지는 다리의 최소 길이를 탐색한다.

이때 탐색한 값을 bridges에 저장하고 정렬해 준다.

3. Kruskal 알고리즘을 사용해 MST ( 최소 스패닝 트리 ) 를 만든다.

 

4. 모든 섬들이 연결 됐는지 검출하는 코드를 작성한다.

 

✅ 코드

---

 

실제 코드를 한 번 살펴보자 

 

import sys
from collections import deque

# board (0,0) -> (row,col)까지 탐색하며 섬을 만나면 flag라는 번호를 붙여 섬을 구분한다.
# 이때 flag라는 번호를 부여하므로 visited라는 list를 사용하지 않아도 된다.
# flag = 2 부터 시작하는데 이는 이미 섬들이 1로 표기되어 있어 문제가 발생하기 때문이다.
def bfs(r,c,flag):
    queue = deque()
    queue.append((r,c))

    while queue:
        y,x = queue.popleft()
        
        if board[y][x] == flag:
            continue
        
        board[y][x] = flag

        for dy,dx in delta:
            ny,nx = y+dy, x+dx

            if 0 <= ny < row and 0 <= nx < col and board[ny][nx]:
                queue.append((ny,nx))
                
# 섬의 경계에서 0으로 나갔을 때 다리의 최소 길이를 찾는 메소드이다.
# 이동하던 방향 (dy,dx)를 계속 더해가며 다리를 찾는다.
# 이때 board 밖으로 벗어나거나 / 시작한 섬의 일부를 만나면 멈춘다.
# board의 값이 0이면 length += 1한다.
# 다른 섬을 만나면 이 간선을 저장 ( length, 섬1, 섬2 ) 형태로 저장한다.
def getDistance(y,x,dy,dx,flag):
    length = 1
    
    while True:
        y += dy
        x += dx
        if y < 0 or y >= row or x < 0 or x >= col:
            return
        if board[y][x] == 0:
            length += 1
        elif board[y][x] == flag:
            return
        else:
            if length <= 1:
                return
            bridges.append((length,flag,board[y][x]))
            return

# 섬의 한 점을 입력하면 그 점이 입력한 섬을 bfs로 탐색하며 섬의 경계를 찾는다.
# 섬의 경계에서는 위의 다리의 최소의 길이를 찾는 getDistance() 를 실행하여 다리를 찾는다.
def findBrdige(r,c,flag):
    queue = deque()
    queue.append((r,c))

    while queue:
        y,x = queue.popleft()
        
        if board[y][x] != flag or visited[y][x]:
            continue
        
        visited[y][x] = True
        board[y][x] = flag

        for dy,dx in delta:
            ny,nx = y+dy, x+dx
            if ny < 0 or ny >= row or nx < 0 or nx >= col:
                continue
            if board[ny][nx] == 0:
                getDistance(ny,nx,dy,dx,flag)
            elif board[ny][nx] == flag:
                queue.append((ny,nx))

# Kruskal 알고리즘을 적용하기 위한 Union - Find 알고리즘이다.
# 주로 그래프가 연결되어 있는지를 확인하기 위해 사용된다.
def find(node):
    if roots[node] == node:
        return node
    
    root = find(roots[node])
    roots[node] = root
    return roots[node]

def union(n1,n2):
    n1,n2 = find(n1),find(n2)

    if n1 == n2:
        return
    elif n1 < n2:
        roots[n2] = n1
    else:
        roots[n1] = n2


row,col = map(int,sys.stdin.readline().rstrip().split())
board = [ list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(row) ]

# 이 visited는 섬을 구분하는 bfs 메소드에서 사용되지 않고
# findBridge 메소드에서 사용된다.
visited= [ [ False for _ in range(col) ] for _ in range(row) ]
delta = ((-1,0),(1,0),(0,1),(0,-1))

bridges = []

# 다리 번호를 부여하기 위한 flag
flag = 2

# 각 섬의 시작점을 저장하기 위한 start_point
start_point = []
for r in range(row):
    for c in range(col):
        if board[r][c] == 1:
            start_point.append((r,c,flag))
            bfs(r,c,flag)
            flag += 1            

# Union Find 를 적용하기 위한 roots
roots = [ i for i in range(flag)]

# 각 섬의 시작점에서 시작해 그 섬에서 다른 섬으로 이어지는 bridge를 찾는다.
for r,c,flag in start_point:
    findBrdige(r,c,flag)

# Kruskal 알고리즘을 사용하기 위해 간선들을 정렬한다.
bridges.sort()

# 결과값을 저장할 result, 최소신장트리인지 확인하는 cnt 변수를 선언한다.
result = 0
cnt = 0
for length,node1,node2 in bridges:
	#다리의 길이가 2보다 작으면 연결하지 않는다.
	if length < 2:
        continue
        
   	# 싸이클이 형성되면 연결하지 않는다.
    if find(node1) == find(node2):
        continue

	else:
        result += length
        union(node1,node2)
        cnt += 1

# 모든 섬이 연결 되었는지 확인한다.
# 섬의 번호를 2 부터 부여하기 때문에 len(roots)에 -3을 해준다.
# 이 때 최소신장트리의 간선의 개수는 node의 개수 - 1이다.
# 그러므로 len(roots) - 3 != cnt 인 경우 최소신장트리가 되기에 간선의 개수가 모자르다.
if len(roots) - 3 != cnt:
    result = -1
print(result)