[백준] 2178번 - 미로 탐색 (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/2178

2178번: 미로 탐색

미리 주어진 미로를 그래프라고 생각하고 주어진 위치 (N, M)까지 최소 거리로 이동하는 문제이다.

전형적인 BFS 문제로 (0, 0)부터 BFS를 시작해서 최종 목적지까지 이동하면 된다.

 

상, 하, 좌, 우로 이동하면서

다음 위치가 범위를 벗어나거나 이미 방문한 경우, 이동할 수 없는 위치인 경우에는 무시한다.

 

만약 이동할 수 있는 곳인데 아직 방문하지 않은 곳이라면 큐에 삽입하고

해당 정점의 값은 현재 내가 머물러 있는 위치의 정점 값에 1을 더한 값을 대입한다.

 

1을 더해서 값을 넣는 이유는 거리를 알기 위해서이다.

최종 목적지까지 가는 동안 내가 몇 걸음이나 왔는지 흔적을 남기는 것이다.

BFS에서는 한번에 한 너비씩 진행하기 때문에 같은 너비라면 같은 값을 가질 것이다.

 

최종 목적지까지 갔을 때 BFS가 종료되면

자연스럽게 마지막 최종 목적지의 값이 도달하는데 필요한 최소 거리가 될 것이다.

 

 

[소스코드]

from collections import deque

n, m = map(int, input().split())

graph = []

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

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


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 ny < 0 or nx >= n or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                queue.append([nx, ny])
                graph[nx][ny] = graph[x][y] + 1


bfs(0, 0)

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