파이선) 미로만들기 - BOJ

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

 

from collections import deque

n = int(input())

arr = []

for i in range(n):
    arr.append(str(input()))


visit = [[False for _ in range(n)] for _ in range(n)]

q = deque()

q.append((0, 0, 0))

visit[0][0] = True

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

while q:
    x, y, cnt = q.popleft()

    if x == n-1 and y == n-1:
        print(cnt)
        break

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y

        if 0 <= nx < n and 0 <= ny < n:
            if visit[nx][ny] == False:
                visit[nx][ny] = True
                if arr[nx][ny] == '1':
                    q.appendleft((nx, ny, cnt))
                else:
                    q.append((nx, ny, cnt+1))

 

문제의 요점은 다음과 같다

1. 흰 방과 검은 방을 탐색한다
2. 흰 방일 시엔 그냥 cnt를 append
3. 만약 검은 방일 시에는 cnt + 1
4. 그러나 흰 방을 모두 찾고 그 다음 검은 방을 찾아야한다. 즉, 어떤 방에서 검은 방을 먼저 popleft시키지 말아야 흰 방의 끝에서 뚫어야 할 검은 방이 append된다. 그러므로 q.append()가 아닌 q.appendleft()로 되어야한다.