[백준] 2178 - 미로 탐색 (Python)

문제 설명

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

2178번: 미로 탐색

 

---

문제 풀이

가장 기본적인 BFS 문제

경로의 최단 거리를 구하는 문제이기 때문에 BFS로 풀었다

만약 경로가 몇 가지인지를 묻는다면 DFS로..!

 

미로 범위에서 벗어난 경우이거나, 이동할 수 없는 칸을 무시하고

해당 칸을 처음 방문했을 때 이전 지점까지의 최단거리 + 1 해주었다

 

from collections import deque

def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    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] == 0:
                continue
            # 해당 칸을 처음 방문하는 경우에만 최단거리 기록
            if graph[nx][ny] == 1:
                graph[nx][ny] += graph[x][y]
                queue.append((nx, ny))

    return graph[-1][-1]

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

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

print(bfs(0, 0))