[백준] 미로 탐색

문제

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

TC

방문 체크를 한다면 같은 정점을 두 번 이상 방문하지 않기 때문에, 모든 정점을 방문하는 시간 + 모든 간선을 확인하는 시간만큼 걸린다.
O(NM)

Idea

가장 빠른 길을 찾는 문제이므로 BFS로 풀면 어려움 없이 풀 수 있다.

code (Python)

from collections import deque

# n * m 크기의 미로
n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -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 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                # 이전 칸보다 1칸 더 가면 된다
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs(0, 0))

self code review

BFS의 기본 문제였던 만큼 가뿐히 풀 수 있던 문제이다. nice~