[백준] #2178 Python 미로탐색 bfs

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

처음엔 dfs로 해서 가능한 거리 리스트화해서 그중 가장 작은거 골라야되는건가 하다가

bfs일텐데.. 하며 count 변수 만들어서 어떻게 증가시켜야 하나 고민하다가

결국 다른 풀이 도움을 받고 그래프 자체를 직전 최단거리 +1 로 수정하면 되는구나! 했다

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().rstrip())))

def printgraph(graph):
    for el in graph:
        print(el)

printgraph(graph)

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

def bfs(graph, i, j):

    q = deque()
    q.append((i, j))

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

                if 0 <= X < N and 0 <= Y < M and graph[X][Y] == 1:
                    q.append((X, Y))
                    graph[X][Y] = graph[x][y] + 1

    return graph[N-1][M-1]

print(bfs(graph, 0, 0))

printgraph(graph)


#넣은 값
4 6
101111
101010
101011
111011
#결과
#입력한 내용 그래프로
[1, 0, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0]
[1, 0, 1, 0, 1, 1]
[1, 1, 1, 0, 1, 1]
#총 최단거리
15
#최단거리로 수정한 그래프
[3, 0, 9, 10, 11, 12]
[2, 0, 8, 0, 12, 0]
[3, 0, 7, 0, 13, 14]
[4, 5, 6, 0, 14, 15]