[백준 2024/09/15] 2178번 미로 탐색

1. 문제

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

 

2. 접근 방법

처음엔 dfs로 코드를 작성하여 재귀로 문제를 해결하고자 하였다.

하지만 지속적인 '시간 초과'가 발생하였고 dfs 를 stack으로 접근해야 하나 라고 생각하게 되었다.

 

def get_maze(y):
    maze = []
    for _ in range(y):
        m = list(input())
        maze.append(m)

    return maze


def get_shortest_path(i, j, path_count):
    global shortest_path
    if i == y-1 and j == x-1 and shortest_path > path_count:
        shortest_path = path_count

    for l, r in udlf:
        if 0 <= i + l < y and 0 <= j + r < x and (not visited[i + l][j + r]) and maze[i + l][j + r] == '1':
            visited[i + l][j + r] = True
            get_shortest_path(i+l, j+r, path_count + 1)
            visited[i + l][j + r] = False


if __name__ == "__main__":
    y, x = map(int, input().split())
    maze = get_maze(y)
    visited = [[False] * x for _ in range(y)]
    visited[0][0] = True
    udlf = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    shortest_path = y * x
    get_shortest_path(0, 0, 1)
    print(shortest_path)

처음에 recursion으로 작성 시도한 코드는 위와 같다.

 

답은 제대로 나올 수 있지만, 모든 경우의 수를 탐색해야 하기에 시간초과가 발생하였다.

따라서, dfs로 작성하되, stack으로 작성해 보자고 생각하게 되었다.

 

 

이렇게 같이 공부한 분이랑, dfs - stack으로 구현해 보려고 하였다.

하지만, 해당 코드는 미로 찾기 경로를 제공할 순 있어도 최단거리를 보장할 수 없다.

위 코드는 

wall = 0, not visited = 1, visited = 2, back_track = 3으로 두고, maze[][]에 값을 수정해 나가면서 작성하였다.

만약 특정 경로에서 더 이상 not_visited 인 값이 없다면, 경로를 저장했던 곳에서 pop을 진행하면서, back_track 값을 저장해 주었다.

 

이 과정을 통해서 

 

DFS는 최단 거리를 보장하지 않는다는 사실을 알게 되었다.

 

마지막으로 BFS를 통해서 코드를 적기 시작하였다. 방문하지 않은 곳이면, 방문할 수 있도록 queue에 넣어주었다.

따라서, 경로 길이에 따라 순차적으로 접근하게 되어, 처음 목적지에 도착하면 해당 경로 거리는 최단 거리를 보장하게 된다.

또한, queue에 값을 저장할 때, 경로 거리도 함께 저장해 주었다.

 

3. 코드

def get_maze(x):
    maze = []
    for _ in range(x):
        m = list(input())
        maze.append(m)

    return maze


def get_min_cost(maze):
    visited = [[False] * y for _ in range(x)]
    visited[0][0] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    queue = [(0, 0, 1)]
    while True:
        i, j, cost = queue.pop(0)
        if i == x-1 and j == y-1:
            return cost

        for l, r in directions:
            if 0 <= i + l < x and 0 <= j + r < y and not visited[i + l][j + r] and maze[i + l][j + r] == '1':
                visited[i + l][j + r] = True
                queue.append((i + l, j + r, cost + 1))


if __name__ == "__main__":
    x, y = map(int, input().split())
    maze = get_maze(x)
    print(get_min_cost(maze))