[백준 알고리즘] 2178번 미로탐색, 파이썬(python)

2178, 미로 탐색

📁 문제 출처

2178번: 미로 탐색

 

💡 생각

• 최소의 칸 수를 출력하기 위해서는 popleft를 한 뒤 4방향을 체크할 때 카운트 된 칸 수 +1로 라벨링 해주면서 끝까지 나아가면 최소 칸 수를 구할 수 있다.

 

🛠 나의 코드

from   collections import deque

n, m = map(int, input().split())
graph = []

for i in range(n):
    graph.append(list(map(int, input())))

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

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

    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))


for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            bfs(graph, i, j)

print(graph[n-1][m-1])

 

✔️ 배운 점 및 주의할 점

• 문제에 있는 [예제 입력 1]을 참고하면 [0][4]에서부터 문제의 시작인데 여기서 [0][5]와 [1][5]를 칸 수 12로 체크해주면서 나아가야 되는 것을 떠올렸지만 어떻게 체크해야 할지 몰라 한참을 고민했다.