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