[백준] 2665번 - 미로만들기 (파이썬)

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

# 미로만들기
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

arr = []
for i in range(N):
    arr.append(list(map(int, input().strip())))


def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[-1] * N for _ in range(N)]
    visited[0][0] = 0
    while q:
        x, y = q.popleft()
        if x == N-1 and y == N-1:
            return visited[x][y]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
                if arr[nx][ny] == 1:
                    q.appendleft((nx, ny))
                    visited[nx][ny] = visited[x][y]
                else:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1


print(bfs())

 

BFS

1. 시작지점(0, 0)에서 bfs를 한다. (visited = 검은 방을 흰 방으로 바꾼 횟수)

    - 해당 위치가 흰 방(1)이면 이전 visited의 값으로 초기화, appendleft(흰 방 먼저 탐색)

    - 해당 위치가 검은 방(0)이면 이전 visited에서 1을 더해서 초기화, append

2. x, y 가 도착지점(N-1, N-1)이면 return visited[x][y]

 

흰 방을 먼저 탐색하기 때문에

처음 도착지점에 도착한 visited의 값은 최솟값이 된다.