백준 문제 풀이 - 미로 탐색 2178번

📜 문제 이해하기

N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

💡 문제 재정의

미로가 주어질 때 가장 빨리 탈출하는 루트의 이동 횟수를 출력하라.

✏️ 계획 수립

가장 쉬운 방법으로는 bfs를 브루트포스로 돌리는 것이다. 먼저 갈 수 있는 후보군들을 전부 bfs를 수행하고 가장 먼저 도착하는 것의 count를 출력하면 된다. 이 때 갈 수 있는 후보군들은 아래 규칙에 따라 정의된다.
1. 미로를 벗어나서는 안된다.
2. 갈 수 있어야 한다. (1일때)
3. 방문하지 않은 곳이어야 한다.

💻 계획 수행

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    maze = []
    for _ in range(N):
        maze.append(list(map(int, sys.stdin.readline().rstrip())))
    candidate_nodes = []
    visited = [[0 for _ in range(M)] for _ in range(N)]
    open_set = [{
        'y': 0,
        'x': 0,
        'count': 1,
    }]
    visited[0][0] = 1

    while open_set:
        node = open_set.pop(0)
        y, x = node['y'], node['x']
        count = node['count']

        if y == N - 1 and x == M - 1:
            print(count)
            break
        if y - 1 >= 0 and maze[y - 1][x] == 1 and visited[y - 1][x] == 0:
            candidate_nodes.append([y - 1, x])
        if y + 1 < N and maze[y + 1][x] == 1 and visited[y + 1][x] == 0:
            candidate_nodes.append([y + 1, x])
        if x - 1 >= 0 and maze[y][x - 1] == 1 and visited[y][x - 1] == 0:
            candidate_nodes.append([y, x - 1])
        if x + 1 < M and maze[y][x + 1] == 1 and visited[y][x + 1] == 0:
            candidate_nodes.append([y, x + 1])

        for candidate_node in candidate_nodes:
            visited[candidate_node[0]][candidate_node[1]] = 1

            open_set.append({
                'y': candidate_node[0],
                'x': candidate_node[1],
                'count': count + 1
            })

        candidate_nodes.clear()

🤔 회고

원래는 택시 기하학을 이용한 휴리스틱한 방법으로 문제를 해결하려고 했으나 거리의 값이 없기 때문에 휴리스틱한 방법으로는 해결하기 어려웠다. 따라서 브루트포스 방법을 사용했지만 더 쉽게 풀 수 있는 방법이 존재할 것 같다.