백준 2146 다리 만들기 Python

🐸 문제 정보

2146번: 다리 만들기

 

🤖 알고리즘

BFS

 

⏱️ 풀이 시간

36.01m

 

📝 풀이

문제가 엄청 복잡해보여서... 무조건 시간초과 or 메모리초과 날거라고 생각했는데 다행히 그렇게 복잡한 문제는 아니었다.

영역 구분할 때 초기 값에 uni를 넣어주는 것을 깜빡해서 1트는 실패했다ㅠ

 

1. 입력값을 BFS 돌면서 영역 구분
2. 구분된 영역을 돌면서, 사방에 바다가 있는 경우 bfs 시작
   • dist 리스트를 통해, 다른 영역까지의 거리를 1씩 더해줌
   • 만약 돌다가 다른 영역 만나면 현재 저장된 거리와 이번 거리 비교해서 최솟값으로 갱신

 

🧑‍💻 나의 답

# pypy3

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
temp = [list(map(int, input().rstrip().split())) for _ in range(n)]
board = [[0] * n for _ in range(n)]
dist = [[0] * n for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
uni = 0
res = sys.maxsize

for i in range(n):
    for j in range(n):
        if (temp[i][j] == 1) and (board[i][j] == 0):
            q = deque([(i, j)])
            uni += 1
            board[i][j] = uni
            while q:
                px, py = q.popleft()
                for d in range(4):
                    nx, ny = px + dx[d], py + dy[d]
                    if (0 <= nx < n) and (0 <= ny < n) and (temp[nx][ny] == 1) and (board[nx][ny] == 0):
                        board[nx][ny] = uni
                        q.append((nx, ny))

for i in range(n):
    for j in range(n):
        if board[i][j] != 0:
            q = deque([(i, j)])
            start = board[i][j]
            while q:
                px, py = q.popleft()
                for d in range(4):
                    nx, ny = px + dx[d], py + dy[d]
                    if (0 <= nx < n) and (0 <= ny < n) and (board[nx][ny] == 0) and (
                            dist[nx][ny] == 0 or dist[px][py] + 1 < dist[nx][ny]):
                        dist[nx][ny] = dist[px][py] + 1
                        q.append((nx, ny))
                    elif (0 <= nx < n) and (0 <= ny < n) and (board[nx][ny] != 0) and (board[nx][ny] != start):
                        res = min(res, dist[px][py])

print(res)