[최소 신장 트리/Python] 17472번: 다리 만들기 2 - 효과는 굉장했다!

17472번: 다리 만들기 2

 

알고리즘 분류

• 구현
• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색
• 최소 스패닝 트리

 

 

SOLUTION

import sys
from collections import deque

# bfs를 통해 각 대륙 고유 라벨링
def bfs(i, j):
    global continent_num
    
    queue = deque([[i,j]])
    island[i][j] = continent_num

    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < M and island[nx][ny] == 1:
                island[nx][ny] = continent_num
                queue.append([nx,ny])


# 섬을 연결하는 일직선 다리 만들기
def make_bridge(section):
    start, length = 0, 0
    state = False

    for idx in range(len(section)):
        # 현재 위치가 땅이면서 아직 다리 시작점이 정해지지 않았을 때
        if section[idx] and not state:
            state = True
            start = section[idx] # 다리의 시작점

	    # 현재 위치가 바다고 다리의 시작점이 이미 정해졌을때 
        elif not section[idx] and state:
            length += 1
            
        # 두 섬사이가 연결되었고 다리의 길이가 2이상 일 때
        elif section[idx] and section[idx] != start:  
            if length >= 2: 
                if (length, start, section[idx]) not in bridges:
                    bridges.append((length, start, section[idx]))

            # 섬이 3개 이상 있으면 또 다른 다리가 만들어질 수 있으므로 값 초기화
            length = 0
            start = section[idx]
        
        elif start == section[idx]: # 이전 칸과 같은 지역의 땅일 경우 
            length = 0


# 크루스칼 알고리즘을 이용해 최소거리를 구한다
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])

    return parent[x] 


def union(a, b):
    root_A = find(a)
    root_B = find(b)

    if root_A < root_B:
        parent[root_B] = root_A
         
    else:
        parent[root_A] = root_B


N, M = map(int, sys.stdin.readline().split())
island = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
continent_num = 1
bridges = []

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(N):
    for j in range(M):
        if island[i][j] == 1:
            continent_num += 1
            bfs(i,j)
            
      
# 각 열과 행에서 구간의 합이 최소 5이상이어야 서로 다른 2개의 섬이 존재
# 시간단축을 위의 조건에 부합할 때만 다리를 만든다
for row in island:
    if sum(row) >= 5: 
        make_bridge(row)
    
for col in zip(*island):
    if sum(col) >= 5:
        make_bridge(col)
        
bridges.sort()
parent = [i for i in range(continent_num+1)]
total, cnt = 0, 0

for i in range(len(bridges)):
    cost, a, b = bridges[i] 
    if find(a) != find(b):
        union(a, b)
        total += cost
        cnt += 1

if cnt == continent_num-2:
    print(total)
    
else:
    print(-1)