[백준] 17472 다리만들기2 (Python)

1. 문제 조건

• 지도는 NxM 이차원 격자(1 <=N, M <=10)
• 섬은 1, 바다는 0으로 입력 받음(2 <= 섬의 개수 <=6)
•  다리를 연결해서 모든 섬을 연결하려 하는데, 이때 다리 길이의 최솟값 구하기(불가능하면 -1 출력)

[다리 생성 조건]

-다리 방향은 중간에 바뀔 수 없음

-다리 길이는 2 이상

 

2. 풀이 전 생각정리

• 일단 각각의  섬들을 다른 섬으로 식별해야 하기 때문에 2부터 라벨링 해보자
  • island_num=2로 세팅한 뒤
  • 이중 for문으로 맵 전체를 돌다가 1을 발견하면 DFS로 1이 있는 영역을 다 island_num으로 만들어준 뒤, island_num+=1
• 섬들을 연결하는 다리에 대한 정보를 길이가 최소인 정보만 남겨서 distance 리스트에 저장
  • 섬의 개수가 최대 6이므로 6*6 이차원 리스트 distance의 모든 요소를 0으로 세팅
  • 다리 생성 조건을 충족시키는 상황이 발생하고, 다리 길이기 기존에 distance에 있는 값보다 작으면 distance에 넣어줌  ex) island_num 2와 3을 연결하는 다리 길이가 2이면 distance [0][1]에 2를 넣어줌(기존 값이 0 혹은 2보다 작은 값일 때)
• distance리스트에는 중복 값, 0이 존재하므로 보기 쉽게 [다리 길이, 섬 번호 1, 섬 번호 2]의 형태로 편집
  • arranged_d = list()
  • distance 리스트를 한 바퀴 돌면서 0이 아닌 값을 발견하면 arranged_d 리스트에 넣어줌
  • 단, arranged_d에 [2,1,2]가 있으면 [2,2,1]은 안 넣어줘도 됨(중복 값이므로)
• 크루스칼 알고리즘을 이용하여 MST구함
• 이렇게 했는데도 섬들이 다 연결되지 않았다면 -1을 출력

 

3. 코드 구현

#map의 크기 -> N행, M열
#다리 조건 -> 방향 바꿀수 없음, 길이 2이상, 교차가능
#육지는 1, 바다는 0
from collections import deque
 
#섬 정보를 2부터 라벨링하는 함수
def labeling(start, mapp, island_num):
    queue = deque()
    queue.append(start)
    
    while queue:
        x,y = queue.popleft()
        mapp[x][y] = island_num
        
        for dx, dy in move_list:
            nx, ny = x+dx, y+dy
            if 0<=nx<N and 0<=ny<M and mapp[nx][ny]==1:
                mapp[nx][ny] = island_num
                queue.append((nx,ny))
 
#간선 정보를 구하는 함수                
def find_edge(x,y,idx):
    for dx, dy in move_list:
        nx, ny = x+dx, y+dy
        count = 0
        while True:
            #벗어나면 break
            if nx<0 or ny<0 or nx>=N or ny>=M: break
            #같은 섬이면 break
            if mapp[nx][ny] == idx: break
            #더 나아갈 수 있으면 한번 더 움직이기
            if mapp[nx][ny] == 0:
                nx += dx
                ny += dy
                count += 1
                continue                
            #벗어나지도 않고, 같은 섬도 아니고, 바다도 아닐 때 -> 다른섬
            if count<2: break
                
            num = mapp[nx][ny]
            cost = distance[idx-2][num-2]
            if cost == 0: distance[idx-2][num-2] = count
            else: distance[idx-2][num-2] = min(cost, count)
            break
            
#부모노드 정보
def getParent(idx):
    if parent[idx] == idx:
        return idx
    parent[idx] = getParent(parent[idx])
    return parent[idx]
 
#병함
def unionParent(a,b):
    a = getParent(a)
    b = getParent(b)
    if a<b: parent[b] = a
    else: parent[a] = b
 
N, M = map(int, input().split())
mapp = []
for _ in range(N):
    mapp.append(list(map(int, input().split())))
    
move_list = [(-1,0),(1,0),(0,-1),(0,1)]
 
distance = [[0 for j in range(6)] for i in range(6)] #섬 갯수 max가 6이므로
arranged_d = []
parent = [i for i in range(6)]
answer = 0
                                                  
#섬을 2부터 라벨링
island_num = 2
for i in range(N):
    for j in range(M):
        if mapp[i][j] == 1:
            labeling((i,j), mapp, island_num)
            island_num+=1
 
#간선 정보 찾기
for i in range(N):
    for j in range(M):
        if mapp[i][j]:
            find_edge(i,j,mapp[i][j])
 
#[다리 길이, 섬 번호1, 섬 번호2] 형태로 데이터 편집
for i in range(6):
    for j in range(6):
        if distance[i][j] and [[distance[i][j],j,i]] not in arranged_d:
            arranged_d.append([distance[i][j],i,j])
 
#weight 기준으로 arranged_distance sort
arranged_d = sorted(arranged_d, key = lambda x: x[0])
 
#크루스칼
for node in arranged_d:
    if getParent(node[1]) != getParent(node[2]):
        answer += node[0]
        unionParent(node[1], node[2])
 
#앞서 union을 할 때 island_num이 작은 것들을 위로 올렸으므로 parent가 모두 0이 아니면 전체가 다 연결X        
for i in range(island_num-2):
    if getParent(i) != 0:
        answer = -1
        break  
        
print(answer)