[백준] 2178번 미로 탐색 파이썬 정답 코드

2178번: 미로 탐색

---

1. 문제 내용

 

 

2. 접근 방식

• 너비 우선 탐색 사용

(1, 1)에서 상하좌우 인접한 칸을 확인하면서 너비 우선 탐색을 한다.

 

• 칸 수는 visited 2차원 리스트로 카운트한다.

(1, 1)의 첫 번째로 방문하는 칸이고, 상하좌우에 붙어 있는 칸을 방문한다면 그것은 두 번째로 방문하는 칸이다. 즉, visited[0][0] = 1이면, 우측에 있는 칸을 방문한다면 visited[0][1] = visited[0][0] + 1 = 1 + 1 = 2로 계산된다.

** 편의상 (1, 1)칸은 (0, 0)칸으로, (N, M)칸은 (N-1, M-1)칸으로 코드를 작성하였다.

 

 

3. 정답 코드

from collections import deque

def bfs(i, j):
    visited[i][j] = 1  # 방문 처리

    queue = deque([[i, j]])

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

        for d in directions:
            dx = x + d[0]
            dy = y + d[1]

            if dx >= n or dx < 0 or dy >= m or dy < 0:
                continue

            if not visited[dx][dy] and maps[dx][dy]:
                visited[dx][dy] = visited[x][y] + 1
                queue.append([dx, dy])

    return visited[n-1][m-1]


# main
n, m = map(int, input().split())
maps = [list(map(int, input())) for _ in range(n)]

visited = [[0] * m for _ in range(n)]
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # up - down - left - right


print(bfs(0, 0))