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

17472번: 다리 만들기 2

 

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12

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

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

 

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

 

코드

from collections import deque
from heapq import heappop, heappush

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))
island_info = [[-1]*m for _ in range(n)]

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


def bfs(x, y, num):  # 섬 구분
    q = deque([(x, y)])
    island_info[x][y] = num
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 같은 섬의 아직 방문 안 한 땅인 경우
                if board[nx][ny] == 1 and island_info[nx][ny] == -1:
                    q.append((nx, ny))
                    island_info[nx][ny] = num


def bfs2(x, y):    # 섬끼리 다리 내리기
    q = deque([(x, y)])
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                # 같은 섬의 아직 방문 안 한 땅인 경우
                if board[nx][ny] == 1 and not visited:
                    q.append((nx, ny))
                    visited[nx][ny] = True
                # 바다인 경우 => 다리 내려보기
                if board[nx][ny] == 0:
                    bridge(nx, ny, i)


def bridge(x, y, d):
    cnt = 1
    nx, ny = x, y
    s = island_info[x-dx[d]][y-dy[d]]
    while True:
        nx += dx[d]
        ny += dy[d]
        cnt += 1
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            return
        # 땅에 닿음
        if board[nx][ny] == 1:
            # 다른 섬에 거리 2 이상 다리 건설 가능
            if s != island_info[x][y] and cnt-1 >= 2:
                e = island_info[nx][ny]
                if (cnt-1, s, e) not in graph:
                    heappush(graph, (cnt-1, s, e))
            return


def find_parent(x, parent):
    if x != parent[x]:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]


def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)

    if a == b:  # 사이클 형성
        return False

    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    return True


# 섬 구분
island_num = 1
for i in range(n):
    for j in range(m):
        # 아직 방문 안한 섬 -> bfs 수행
        if board[i][j] == 1 and island_info[i][j] == -1:
            bfs(i, j, island_num)
            island_num += 1

# 다리 내리기
graph = []  # 섬끼리 거리
visited = [[False]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if not visited[i][j] and board[i][j] == 1:
            bfs2(i, j)

# MST 구성
ans = 0
connect = 0  # 섬들간 연결의 개수
parent = [i for i in range(island_num+1)]
while graph:
    dist, s, e = heappop(graph)
    if union_parent(s, e, parent):
        ans += dist
        connect += 1

print(ans if connect == island_num-2 else -1)

BFS+MST를 이용한 구현 문제였다.

위 코드는 크게 3부분으로 나눌 수 있다.
섬들을 파악하여 번호를 부여하는 1번째 부분, 섬에서 다른 섬으로 다리를 내리는 2번째 부분, 가장 최소의 거리로 다리를 건설하여 MST를 만드는 3번째 부분. 

 

1. 섬 번호 부여
   • BFS를 이용하여 island_info 2차원 배열에 섬 번호들을 표시한다. island_info 배열에 바다는 -1으로 표시되어 있고, 섬들은 1부터 순서대로 번호를 부여받는다.
2. 섬끼리 거리 계산
   • island_info 배열에 표시한 각 섬을 BFS로 탐색하며 바다가 나오면 bridge 함수를 실행시킨다.
   • bridge 함수는 일직선으로 다리를 건설해서 조건에 맞게 건설할 수 있는 경우 최소힙 graph에 (다리 길이, 시작 섬 번호, 도착 섬 번호) 튜플로 넣어준다.
3. 섬끼리 MST 만들기
   • 크루스칼 알고리즘을 이용하여 MST를 만든다. 앞과정에서 거리 오름차순으로 graph에 저장해주었으니 하나씩 heappop해주며 이미 포함된 노드가 아니라면, 즉 사이클을 만들지 않는다면 MST에 포함시켜준다. 사이클이 생성되는지 여부는 union-find 알고리즘을 이용한다. 
   • MST는 노드의 개수가 n개일 때, 간선의 개수는 n-1개이다. 모든 섬이 연결되었는지 알아보기 위해 connect==island_num-2를 확인하여 답을 출력한다. 이 때 island_num에서 2를 빼는 이유는 island_num에는 현재 섬의 개수보다 1이 큰 숫자가 저장되어있기 때문이다.