백준 2178 미로 탐색 (파이썬)

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

2178번: 미로 탐색

 

문제를 풀 때 배열을 하나 더 선언하여 경로 값을 계산해야 정확한 결과가 출력됩니다.

초기에 변수 하나를 선언해 조건 만족시 경로를 더해가는 방식으로 구현했다가 정확한 결과가 나오지 않아 문제 해결하는데 시간이 좀 걸린 문제입니다.

 

from collections import deque
 
 
def bfs(x, y):
    dq = deque()
    dq.append([x, y])
    while dq:
        x, y = dq.popleft()
        if x == N - 1 and y == M - 1:
            chk[x][y] += 1
            break
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] == 1 and not visit[nx][ny]:
                dq.append([nx, ny])
                visit[nx][ny] = True
                chk[nx][ny] = chk[x][y] + 1
# cnt += 1 << 모든 경로 추적이 누적되어 오답 발생

N, M = map(int, input().split())  # 1 이동가능 0 이동 불가능
maze, visit = [], [[False for _ in range(M)] for _ in range(N)]
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
chk = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
    maze.append(list(map(int, input().rstrip())))
bfs(0, 0)
print(chk[N-1][M-1])
 
# https://www.acmicpc.net/problem/2178