[python] 백준 2146 다리 만들기

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

2146번: 다리 만들기

 

문제 해결

• 섬을 어떻게 구별할 것인가? → 연결 되어 있는 섬을 1, 2, 3 ... 으로 카테고리별로 구분하도록 한다.(0은 바다)
• 섬끼리 거리를 어떻게 측정할 것인가? → 동, 서, 남, 북으로 이동시켜서 바다부분에서 거리를 +1씩 더한다음 출발점고 다른 새로운 카테고리 대륙이 나오면 이전의 기록된 최소 거리와 비교해서 최소거리를 ans로 저장을 한다. 이를 bfs를 통해서 계속 진행한다.

CODE

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
mapping = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
move = [(-1,0), (1,0), (0,1), (0,-1)]
cnt = 1
ans = sys.maxsize
# 섬을 구분해주는 bfs
def bfs1(i, j):
    global cnt
    q = deque()
    q.append([i, j])
    visited[i][j] = 1
    mapping[i][j] = cnt

    while q:
        x, y = q.popleft()
        for k in range(len(move)):
            new_x = x + move[k][0]
            new_y = y + move[k][1]
            if 0<= new_x <n and 0<=new_y<n and mapping[new_x][new_y] ==1 and visited[new_x][new_y] == 0:
                visited[new_x][new_y] = 1
                mapping[new_x][new_y] = cnt
                q.append([new_x, new_y])
# 섬끼리 최소 거리 측정
def bfs2(z): # 출발점은 카테고리가 z인 섬의 점
    global ans
    dist = [[-1]*n for _ in range(n)]
    q = deque()
    for i in range(n):
        for j in range(n):
            if mapping[i][j] == z:
                q.append([i,j])
                dist[i][j] = 0 # 카테고리가 z인 섬은 dist가 0이다. 같은 섬 이동이므로
    while q:
        x, y = q.popleft()
        for i in range(len(move)): # 동서남북 이동
            new_x = x + move[i][0]
            new_y = y + move[i][1]
            if new_x<0 or new_x>= n or new_y<0 or new_y>=n: # 지도 이탈
                continue
            if mapping[new_x][new_y] > 0 and mapping[new_x][new_y] != z: # 다른 섬까지 연결됨
                ans = min(ans,dist[x][y])
                return
            if mapping[new_x][new_y] == 0 and dist[new_x][new_y] == -1: # 바다이면서 지나가지 않은 거리
                dist[new_x][new_y] = dist[x][y] + 1
                q.append([new_x, new_y])
for i in range(n):
    for j in range(n):
        if visited[i][j] ==0 and mapping[i][j] == 1:
            bfs1(i,j)
            cnt += 1
for i in range(1, cnt):
    bfs2(i)
print(ans)