[백준] 2178 미로 탐색 Python

[백준] 2178 미로 탐색 Python

전형적인 탐색 문제로, BFS와 DFS를 사용하면 된다.
보통, 최소 칸 수를 구하는 프로그램이라 BFS를 사용하면 된다.

문제를 풀면서 고민했던 부분은, visited 배열을 만들어서 갔던 곳을 체크하고 얼만큼 이동했는지 알 수 있도록 cnt를 별도로 선언을 할까 고민했다.
메모리 낭비를 하지 않기 위해 graph 값을 바꾸기로 했다. 첫번째 시작 칸에서 한 칸 이동 후, 다시 돌아오는 경우는 어떻게 해결할까 고민했지만 괜찮았다. bfs를 실행할 때 1인 다음 갈 grpah의 값이 1인 경우만 이동하도록 하면 된다.

from collections import deque
import sys
sys.stdin=open("input.txt")

n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input())))


#북동남서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs(graph,si,sj):
    q=deque()
    q.append((si,sj))

    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                q.append((nx,ny))


bfs(graph,0,0) #시작은 1,1이지만 graph 상에서는 0,0인 것을 주의하자!
print(graph[n-1][m-1])