백준 2146 다리 만들기 파이썬 풀이

난이도 : 골드3

풀이일 : 07053

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

2146번: 다리 만들기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이 코드

import sys
from collections import deque

# 섬 고유번호 설정 함수
def islandnum(a, b, num):
    queue = deque()
    queue.append((a, b))
    while queue:
        i, j = queue.popleft()
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < N and 0 <= nj < N and world[ni][nj] == 1:
                world[ni][nj] = num
                queue.append((ni, nj))
    return

# 다리 구축 함수
def bridge(a, b, num):
    queue = deque()
    queue.append((a, b))
    visited = [[0]*N for _ in range(N)]
    visited[a][b] = 1
    while queue:
        i, j = queue.popleft()
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < N and 0 <= nj < N and not visited[ni][nj]:
                # 바다
                if not world[ni][nj]:
                    visited[ni][nj] = visited[i][j] + 1
                    queue.append((ni, nj))
                # 다른 섬
                if world[ni][nj] and world[ni][nj] != num:
                    return visited[i][j] - 1
    return N ** N

N = int(sys.stdin.readline().strip())
world = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

island = 2
mini = N ** N

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]

# 섬 고유번호 설정
for x in range(N):
    for y in range(N):
        if world[x][y] == 1:
            world[x][y] = island
            islandnum(x, y, island)
            island += 1

# 다리 구축
for x in range(N):
    for y in range(N):
        if world[x][y]:
            mini = min(mini, bridge(x, y, world[x][y]))

print(mini)

코드 구성

• 섬 구분을 위한 고유 숫자 설정 함수 BFS
• 서로 다른 섬 사이의 다리 구축 함수 BFS
  • 바다를 만나면 다리 길이를 늘림
  • 다른 섬을 만나면 다리 길이 반환
• 주어진 세계에서 1을 만나면 해당 칸과 연결된 지역 숫자 변경을 위한 함수 실행
• 주어진 세계에서 땅을 만나면 다리 구축 함수 실행

---

느낀점

BFS를 두 번 사용해서 풀었다.

한 번 틀렸던 문제인데 너무 오래전에 시도했던 문제라 잘 기억도 나지 않는다. 틀리면 메모해둬야겠다.

너무 오랜만에 파이썬 문제를 풀어서 기분이 좋다. 그냥 티어 높은 문제를 풀어서인 것 같지만ㅎㅎ

앞으로는 자바 문제랑 같이 파이썬 문제도 꾸준히 풀어야지