[백준/17472/파이썬] 다리 만들기 2

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

Problem

• 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

조건

• 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
• 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
• 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 
• 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

SOL

 

구현해야할게 정말 많은 문제이다. 하지만, 프로그래머라면! 이런 문제에 익숙해져야 한다! (탈컴공할까?)

생각해봐야할걸 우선 정리해보자.

1. map이 주어진다면, 어떻게 섬을 파악할 것인가?
   • 모든 행위는 섬 to 섬으로 가는 다리를 건설하는 과정에 제약사항이 걸려있다. 이 "섬"이라는 개념을 어떻게 컴퓨터에 인식시킬까?
     • 섬을 인식시키는건 아주 많이 해본 문제이다. BFS/DFS로 연결요소를 찾으면 된다. 단, 여기서는 섬끼리 구분하기 위해서, numbering을 하든, 자신이 알아볼 수 있는 Symbol을 표시해주도록 하자.
     • Island가 최대 6개까지니까, 또 다른 2차원 맵을 만들어도 좋지만, 접근성을 높이기 위해서, dictionary형태로 만들어줄거다. (좌표 : 섬 번호) , 그리고, land_list를 만들어줘서, land에 대한 정보를 담아줄거다.
   • 섬이란걸 파악했다면, 한쪽 섬에서 이제 다리를 건설하기 위해 시뮬레이션을 해줘야하는데, 이 출발지점을 어떻게 정해줄것인가?
     • land_list에 있는거 하나하나 다 돌아줄거임. (n*m =100이기때문에, 최대 100개다. 상관 x)
2. 다리 건설을 어떻게 진행할 것인가 ?
   • 다리 건설할때, 조건은 문제에 주렁주렁 잘 달려있다. 저걸 구현하기만 하면 되는데, 방향이 중간에 바뀌면 안되고, 다리의 길이가 2이상이어야 한다. 이 2가지 조건만 잘 구현하면 될 것 같다.
     • land List에 있는거 하나씩 돌아줄 때, 좌표를 움직이는 시뮬레이션도 같이 곁들여준다.
     • 그리고, 한 방향을 정했다면, 계속 그 방향으로 가야하므로, map의 범위를 벗어나지 않는이상 섬을 만나거나/ 자기자신의 섬으로 돌아오거나/다리의 길이가 2이하이지 않는 이상 계속 반복을 해줘야한다.
3. 모든 섬이 연결되어있는 경우는 어떻게 확인할 것인가?
   • 모든 섬이 연결되는 경우에서 최솟값을 찾아야한다. 다리를 하나 배치하고 ,그때마다 모든 섬이 연결되어있는지 검사를 해야할까? 
   • 이 부분은 크루스칼 MST를 이용해준다.

# 다리를 만들어 봅시다.
import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
maps=[list(map(int,input().split())) for _ in range(N)]
visited=[[False]*M for _ in range(N)]
land = dict()
land_list=[]
landNum=0
dx=[0,1,0,-1]
dy=[1,0,-1,0]

def is_valid_coord(y,x):
    return (0<=y<N and 0<=x<M)

def _make_Island(y,x):
    global landNum
    dq=deque()
    dq.append((y,x))
    visited[y][x] = True
    land[(y,x)] = landNum
    land_list.append((y,x,landNum))
    while dq:
        y,x = dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if is_valid_coord(ny,nx) and not visited[ny][nx] and maps[ny][nx]:
                dq.append((ny,nx))
                visited[ny][nx] = True
                land[(ny,nx)] = landNum
                land_list.append((ny,nx,landNum))


for i in range(N):
    for j in range(M):
        if maps[i][j] ==1 and not visited[i][j]:
            _make_Island(i,j)
            landNum+=1

#다리 제작
edges=[]
for y,x,curLand in land_list:
    for k in range(4):
        dist=0
        ny=y+dy[k]
        nx=x+dx[k]
        while True:
            if is_valid_coord(ny,nx):
                toLand = land.get((ny,nx))
                #같은 섬
                if curLand==toLand:
                    break
                # 바다일 떄
                if toLand==None:
                    # 왔던 방향 그대로 더해준다
                    ny+=dy[k]
                    nx+=dx[k]
                    dist+=1
                    continue
                # 다리를 건설 해봤는데, 2이하이다. 그 다리는 건설하지 않는다.
                if dist <2:
                    break
                edges.append((dist,curLand,toLand))
                break
            else:
                break

edges.sort(reverse=True)

def union(x,y):
    x = find(x)
    y = find(y)
    parents[y] = x

def find(k):
    if k != parents[k]:
        parents[k] = find(parents[k])
    return parents[k]

ans = 0
cnt = landNum-1
parents = [i for i in range(landNum)]
while cnt:
    try:
        w,a,b = edges.pop()
    except:
        # empty list, 다리 부족
        print(-1)
        sys.exit()
    if find(a) != find(b):
        union(a,b)
        ans += w
        cnt-=1
print(ans)