백준 2146 | 다리 만들기 | python 풀이

문제

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

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

 

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

 

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

 

 

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

내 답안

# 2146 다리 만들기
from collections import deque

n = int(input().strip())
graph = [list(map(int, input().split())) for _ in range(n)]

direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
inum = 2  # 육지번호
ans = int(1e9)  # 최단거리


# 대륙 번호 넘버링
def island_numbering(i, j):
  d = deque([(i, j)])

  while d:
    cx, cy = d.popleft()
    graph[cx][cy] = inum
    for dx, dy in direction:
      nx, ny = dx + cx, dy + cy
      if (0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1):
        graph[nx][ny] = inum
        d.append((nx, ny))


# 다리 짓기
def shortcut(inum):
  # 각 대륙마다 최단거리 탐색
  d = deque([])
  dist = [[-1] * n for _ in range(n)]

  for i in range(n):
    for j in range(n):
      if graph[i][j] == inum:
        dist[i][j] = 0
        d.append((i, j))  # inum에 해당하는 육지들 전부 저장

  # 최단거리 탐색
  while d:
    cx, cy = d.popleft()
    for dx, dy in direction:
      nx, ny = cx + dx, cy + dy
      if (0 <= nx < n and 0 <= ny < n):
        # 아직 방문 하지 않은 바다라면
        if (graph[nx][ny] == 0 and dist[nx][ny] == -1):
          dist[nx][ny] = dist[cx][cy] + 1
          d.append((nx, ny))

        # 다른 대륙에 도착했다면
        elif graph[nx][ny] > 0 and graph[nx][ny] != inum:
          return dist[cx][cy]

  return int(1e9)


for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      island_numbering(i, j)
      inum += 1

# 가장 짧은 다리 길이 찾기
for num in range(2, inum):
  temp = shortcut(num)
  ans = min(ans, temp)

print(ans)

해설

이 문제 풀이의 핵심은,

1. 각 대륙을 구분지을 때(island_numbering)

2. 최단 길이의 다리를 탐색할 때(shortcut)

 

를 구분해서 bfs를 2번 돌려줘야 한다는 것이다.

 

대륙을 구분짓는 island_numbering 함수부터 살펴보자.

방문 여부를 기록하는 visited 리스트를 따로 만들지 않고, 바로 graph에 대륙 번호를 저장한다.

(이때 육지를 1 바다를 0으로 표시하므로, 대륙 번호는 2부터 시작한다.)

graph 값이 1인 육지가 있다면 해당 위치에서 시작해서 bfs로 인접한 육지를 찾아나서며 graph에 대륙 번호를 저장한다.

 

최단 길이의 다리를 찾는 shorcut의 경우, 거리 정보를 저장할 dist 리스트를 준비한다.

이후 대륙번호를 for문으로 순회하며 해당 대륙에서 타대륙까지의 최단 거리를 구한다.

바다를 건널 때마다 dist 값을 1씩 증가시켜 저장하고, 가장 먼저 타 대륙에 도착할 때 while문을 종료하고 dist 리스트값을 반환해주면 된다. 

 

 

피드백

• 대륙에 번호를 매겨 구분짓는 것까지는 생각해냈으나 최단 길이를 구하는 과정에서 애먹었다.