[백준, 2178번] 미로 탐색

코드는 빨리 작성이 되었는데
계속 시간 초과가 발생해서 찾아본 결과...
BFS는 `원소를 넣기 전에 방문 처리를 해야 한다`라는 것을 확인 후
회로를 돌려보니 맞는 말이었다.

예를 들어 아래와 같은 미로가 있다고 했을 때 
11
11

q를 통해 (0,0)부터 넣게 된다면 
0,0 = [ [1, 0], [0, 1] ]
1,0 = [ [0, 1], [1, 1] ]
0,1 = [ [1, 1], [1, 1] ]
위와 같이 되는데 이 때 0,1의 경우에 보면 [1,1] 방문 처리를 미리하지 않았기에
중복으로 들어가게 되는 것을 확인할 수 있다.
이유는 한 길로만 쭉 가는게 아니라 갈 수 있는 곳은 다 탐색하면서 가기에 그렇다. 

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
arr = [list(map(int,input().rstrip('\n'))) for _ in range(n)]
visit = [[0]*m for _ in range(n)]
result = n*m
# bfs
q = deque([[0,0,0]])
visit[0][0] = 1
while q:
    x,y,cnt = q.popleft()
    if (x,y) == (n-1,m-1) and result > cnt:
        result = cnt
        break
    elif cnt >= result: continue
    for i,j in [[-1,0], [1, 0], [0, -1], [0, 1]]:
        dx, dy = x+i, y+j
        if 0<=dx<n and 0<=dy<m and arr[dx][dy] and not visit[dx][dy]: 
            visit[dx][dy] = 1
            q.append([dx,dy,cnt+1])
print(result+1)