문제
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 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
n, m = list(map(int, input().split()))
arr = [[0] * m for _ in range(n)]
for a in range(n):
data = list(map(int, input().split()))
for b in range(m):
arr[a][b] = data[b]
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
LAND = 1
SEA = 0
# lands=[(x,y,라벨 번호)]
lands = []
# edges = [ ( 비용, 출발지 , 목적지 )]
edges = []
# (x,y)좌표가 올바른 배열 범위 안에 있는지 확인하는 함수
def is_right_range(x: int, y: int):
if 0 <= x < n and 0 <= y < m:
return True
else:
return False
# bfs 활용해서 각 섬의 영역을 1 이상의 숫자로 라벨링 합니다.
def label_by_bfs(x: int, y: int, land_num: int, visited: list[list[bool]]):
queue = deque()
visited[x][y] = True
queue.append((x, y))
while queue:
row, column = queue.popleft()
arr[row][column] = land_num
lands.append((row, column, land_num))
for k in range(4):
adj_row = row + dx[k]
adj_column = column + dy[k]
if not is_right_range(adj_row, adj_column):
continue
if not visited[adj_row][adj_column] and arr[adj_row][adj_column] == LAND:
visited[adj_row][adj_column] = True
queue.append((adj_row, adj_column))
# 방향을 유지한채로 간선 만들기.
def make_edge(x: int, y: int):
queue = deque()
for direction in range(4):
queue.append((x + dx[direction], y + dy[direction], 1, direction))
while queue:
i, j, distance, direction_going = queue.popleft()
# 해당 방향이 적절한 배열 범위를 넘어서는 경우, 스킵한다.
if not is_right_range(i, j):
continue
# 해당 방향 진행 도중, 같은 라벨 번호의 지역을 만났다면, 스킵한다.
if arr[i][j] != SEA and arr[i][j] == arr[x][y]:
continue
# 해당 방향 진행 도중, 다른 라벨 번호의 지역을 만났다면, (바다 제외) 스킵한다.
if arr[i][j] != SEA and arr[i][j] != arr[x][y]:
if distance > 2: # 만약 거리도 2 초과했다면, 간선에 담아준다.
# 도착지인 섬 영역 1칸은 제외해야 하므로 distance -1 해줘서 간선에 담는다.
# 중요한 점은, 중복되는 간선이 존재한다는 것이다.
# 예를 들어, 2에서3으로 가는 간선과 3에서 2로 가는 간선이 같을 수가 있다.
# 하지만, MST 안의 union and find 연산에 의해 걸러지기 때문에 중복 간선을 담아줘도 무방하다.
edges.append((distance - 1, (x, y), (i, j)))
continue
# 해당 방향으로 1칸 전진한 것을 큐에 담아준다.
queue.append((i + dx[direction_going], j + dy[direction_going], distance + 1, direction_going))
def find_parent(parent: list[int], x: int):
if x != parent[x]:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent: list[int], p: int, q: int):
p = find_parent(parent, p)
q = find_parent(parent, q)
if p > q:
parent[p] = q
else:
parent[q] = p
visit_check = [[False] * m for _ in range(n)]
# 라벨 번호는 2부터 시작한다.
land_label = 2
# 반면, 노드의 개수는 0부터 시작해야 하므로 초깃값은 0.
land_count = 0
# 땅에 대해 라벨링 해본다.
for a in range(n):
for b in range(m):
if not visit_check[a][b] and arr[a][b] == LAND:
label_by_bfs(a, b, land_label, visit_check)
land_label += 1
land_count += 1
# [(x,y,라벨 번호)]에 대해 간선을 만들어본다.
for a, b, label_number in lands:
make_edge(a, b)
# MST 알고리즘 적용
edges.sort()
parent = [i for i in range(land_label)]
answer = 0
edge_count = 0
for cost, origin, destination in edges:
origin_x, origin_y = origin
dest_x, dest_y = destination
if find_parent(parent, arr[origin_x][origin_y]) != find_parent(parent, arr[dest_x][dest_y]):
union_parent(parent, arr[origin_x][origin_y], arr[dest_x][dest_y])
answer += cost
edge_count += 1
# MST 에서 간선 연결된 개수가 노드 개수 -1이 아니라면, 전체 연결된 것이 아니다.
if answer == 0 or edge_count != land_count - 1:
print(-1)
else:
print(answer)
P.S. 나중에 다시 풀어보자. 좋은 문제임.
