BOJ 2178번 - 미로 탐색

[백준 온라인 저지 링크]

2178번: 미로 탐색

문제 분류가 BFS로 되어있어 별 생각없이 BFS로 탐색을 구현했지만, DFS를 사용하면 시간 초과가 난다고 한다.

DFS를 사용하는 코드는 약간 백트래킹? 하듯이 분기별로 값을 저장해둔 뒤 저장한 값들 중 최솟값을 구하면 될 듯 한데...

나보다 잘 짜는 사람들이 안된다는 데에는 이유가 있을 것이다. (_ _)

 

아무튼 최단거리를 구하는 문제는 BFS 방식을 사용하는 것이 정석이라고 한다.

앞으로 비슷한 유형은 BFS를 열심히 우려먹자.

(예전에 얼핏 어떤 문제 유형은 BFS와 DFS중 하나로밖에 풀지 못한다는 내용을 바킹독님 블로그에서 본 것 같은데, 아마 이거인듯 하다.)

 

[정답 코드 - Python]

from collections import deque

N, M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]
visited = [[False] * M for _ in range(N)]

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


def BFS(start_node):
    y, x = start_node # 튜플형을 사용하면 둘 이상의 매개변수도 쉽게 분해할 수 있다.
    queue = deque()
    queue.append((y, x))
    visited[y][x] = True

    while len(queue) != 0:
        curY, curX = queue.popleft()
        for i in range(4):
            nextY = curY + dy[i]
            nextX = curX + dx[i]
            if 0 <= nextY < N and 0 <= nextX < M:
                if visited[nextY][nextX] == False and maze[nextY][nextX] != 0:
                    visited[nextY][nextX] = True
                    queue.append((nextY, nextX))
                    maze[nextY][nextX] = maze[curY][curX] + 1


BFS((0, 0))
print(maze[N - 1][M - 1])

카운트 변수를 사용하면 단순히 미로의 1이 몇 개나 있는지 찾는 것에 불과하다.

대신 다음에 밟는 미궁의 좌표에 도달하는데 몇 개의 경로를 거쳤는지 메모해주기만 하면 된다.

(DFS와는 달리, 모든 방향으로 한 칸씩 뻗어나므로 이상한 루트를 빙글빙글 돌 걱정은 하지 않아도 된다!)