깊이/너비 우선 탐색(DFS/BFS) > 게임 맵 최단거리

문제 위치 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

DFS로 시도를 계속해서 틀렸던 문제이다.

문제가 최단거리를 묻고 있기 때문에 깊이를 반환하는 DFS로 탐색하는 것이 올바른 해결방법이라 생각하였다.

하지만, 결론은 BFS로 문제를 풀어야 하였다.

 

이유는 시간 복잡도 때문이다. 

 

DFS는 특정 경로를 끝까지 탐색한 후에야 다른 경로를 탐색한다. 깊이를 우선으로 탐색하기 때문에, 최단 경로를 알기 위해서 DFS는 경로를 모두 탐색해야 최단 경로를 알 수 있다. 모든 경로를 탐색해야 하므로, 최악의 경우 시간복잡도 O(2^(N×M))가 될 수 있다.

 

BFS는 이와 달리 단계별로 탐색이므로 동일한 거리의 모든 노드를 먼저 탐색하고, 이후로 더 먼 거리를 탐색한다. 따라서, 목표 노드에 도달하는 그 순간이 최단 노드인 것이다. 따라서 목표 지점에 도달하는 순간, 더 이상 다른 경로를 탐색할 필요 없이 종료할 수 있다. BFS의 시간복잡도는 O(V+E)로 DFS보다 효율적이다.

 

아래는 이에 따라 BFS로 탐색을 구현한 것이다. 원래는 자료형을 pair로 좌표를 해당 pair와 거리를 다시 pair로 묶어서 하려 하였으나 tuple이라는 자료형이 있어 이를 사용하였다.

 

tuple은 처음 선언한 사이즈 만큼의 자료를 담을 수 있는 자료형이다.

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

int solution(vector<vector<int>> maps) {
    int n = maps.size();
    int m = maps[0].size();
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<tuple<int, int, int>> q;
    q.push({0, 0, 1});
    visited[0][0] = true;

    while (!q.empty()) {
        int x, y, dist;
        tie(x, y, dist) = q.front();
        q.pop();

        if (x == n - 1 && y == m - 1) {
            return dist;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, dist + 1});
            }
        }
    }

    return -1;
}