백준 2178번 미로 탐색

https://www.acmicpc.net/problem/2178
실패이유 : 구현실패

import collections


def bfs(x, y):
    queue = collections.deque([])

    queue.append((x, y, 1))         # x, y 좌표와 몇 번째 거리인지를 저장
    visit[y][x] = True

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

        if y == h - 1 and x == w - 1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < w and 0 <= ny < h:
                if graph[ny][nx] == "1" and not visit[ny][nx]:
                    queue.append((nx, ny, cnt + 1))             # 거리를 추가
                    visit[ny][nx] = True


h, w = map(int, input().split())
graph = [list(input()) for _ in range(h)]
visit = [[False] * w for _ in range(h)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

print(bfs(0, 0))

• 최단거리 계산은 DFS로 불가능
• BFS 로 계산할 수 있다.
  • 
  • 좌표와 거리값을 튜플로 큐에 넣어준다.
  • 큐에 다음 좌표를 넣을때마다 거리값을 1씩 증가시킨다.
• 원하는 좌표에 도착하면 BFS 탐색을 종료한다.

출처 : 코드플러스 - 알고리즘 기초 2/2 강의
https://code.plus/course/42