[BOJ] 미로탐색(python)

문제 링크 - https://www.acmicpc.net/problem/2178

사고 과정

• 코테 스터디를 진행하며 DFS/BFS 위주로 문제를 풀 때 개념이 제대로 잡혀있지 않은 상태에서 문제를 풀다보니 어려워 답을 보고 풀었었다.
• 입력값으로 graph를 만들어주고, bfs를 통해 주변을 탐색하면서 1이면 그 전 자리의 값에서 +1을 해주었다.
• 그렇게 마지막까지 다 탐색하고 마지막칸의 값을 출력하면 된다.

나의 풀이(답 참고)

from collections import deque

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

def bfs(a,b):
    queue = deque()
    queue.append((a,b))

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

    while queue:
        x, y = queue.popleft()

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

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    return graph[n-1][m-1]
print(bfs(0, 0))