Algorithm & Data Structure
[백준] 다리 만들기 2 (17472번) - Python / MST ( Kruskal Algorithm )
후뿡이
2023. 6. 12. 12:19
✅ 문제 - [백준] 다리 만들기 2 (17472번)
✅ 필요 알고리즘 개념 - BFS / MST ( Kruskal Alogorithm )
🎯 크루스칼 알고리즘( Kruskal Alghrithm ) 이란?
크루스칼 알고리즘이란, 그래프 자료구조에서 그리디 알고리즘을 적용해 MST ( Minimum Spanning Tree , 최소 신장 트리 )를 찾는 방법이다.
그리디 알고리즘의 경우 순간의 최선의 선택이 결과적으로 최선의 선택임을 증명해야 하는데
MST를 푸는 알고리즘 중 프림(Prim's) 알고리즘과 크루스칼(Kruskal) 알고리즘은 그리디 알고리즘이므로 해결 가능함이 이미 증명이 된 알고리즘이다.
크루스칼 알고리즘을 적용하는 순서는 다음과 같다.
- 간선을 리스트에 ( 길이, 노드1, 노드2 ) 형식으로 저장한다.
- 간선을 저장한 리스트를 길이가 짧은 순으로 정렬한다.
- 모든 간선을 탐색해 나가며 길이가 작은 값 부터 선택해 나가며 노드들을 연결해 나간다.
- 연결하는 도 중 싸이클이 형성 되는 경우에는 그 노드는 연결하지 않고 지나간다
- ( 이 때 싸이클 형성은 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)