[C++] Boj 13549 숨바꼭질 3

문제 링크

[13549 숨바꼭질 3]

접근 및 해결

일반 bfs 방법으로 풀려고 했으나 계속 틀려서 질문 게시판을 찾아 보았다.

이 문제에서는 간선의 가중치가 다르기 때문에, 먼저 도착했더라도 그 경로가 최소임을 보장할 수 없다.

초기 코드 - 실패

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 100000 + 1;
int board[MAX];
int N, K;
int dx[2] = {-1, 1};
int main()
{
    cin >> N >> K;

    queue<int> q;
    q.push(N);
    board[N] = 1;

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        if (cur == K)
        {
            cout << board[K] - 1 << endl;
            return 0;
        }
        
        for (int next : {cur - 1, cur + 1, cur * 2})
        {
            if (next >= 0 && next < MAX && !board[next])
            {
                board[next] = (next == cur * 2) ? board[cur] : board[cur] + 1; // 순간이동 비용 처리
                q.push(next);
            }
        }
        
    }
}

그럼 가중치가 다를 때 BFS는 어떻게 처리해야 하는가?

• 다익스트라
• 0- 1 bfs

보통 다익스트라 알고리즘을 많이 사용한다고 한다. 하지만 이 그래프는 가중치가 0, 1이므로 0-1 bfs 알고리즘을 이용할 수도 있다. 따라서 두 가지 방법으로 다 풀어보겠다! 우선 개념부터 알고 가자.

다익스트라 알고리즘

1-1. 개요

다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

참고로 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

1-2. 동작 단계

① 출발 노드와 도착 노드를 설정한다.

② '최단 거리 테이블'을 초기화한다.

③ 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.

④ 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트한다.

⑤ ③~④의 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개(1부터 시작하는 노드 번호와 일치시키려면 N + 1개) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.

'노드 방문 여부 체크 배열'은 방문한 노드인지 아닌지 기록하기 위한 배열로, 크기는 '최단 거리 테이블'과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

1-3. 동작 예

 

출발 노드는 1번, 도착 노드는 6번이라 하고 거리 테이블을 전부 큰 값, 여기서는 inf(무한대)로 초기화했다. 각 노드들을 잇는 간선의 가중치 역시 표시했다.

출발 노드를 먼저 선택하고 거리를 0으로 한다.

1번 노드와 연결된 인접 노드는 2, 4이다. 그곳까지 가는 거리를 각각 기존의 거리값과 비교해 최솟값으로 업데이트한다. 가령 2의 경우 inf와 2 중 작은 값인 2를 택해 할당한다.

또한 인접 노드까지의 거리를 모두 업데이트한 1번 노드는 방문 표시를 한다.

최근 갱신한 테이블 기준, 방문하지 않는 노드 중 가장 거리값이 작은 번호를 다음 노드로 택한다. 위 상태에서는 4번 노드이다.

4번 노드에서 같은 작업을 수행한다. 4번과 연결된 2, 5번까지 오는 거리를 계산한다. 가령 5의 경우엔 4번까지 오는 데 필요한 거리 + 4->5 간선의 가중치 값인 2와 기존의 값인 inf 중 최솟값을 계산하고, 2번 노드의 경우엔 기존 값인 2와 4번을 거쳐가는 값인 1+2 = 3을 비교한다. 그렇다면 2번 노드는 기존 값이 더 크므로 업데이트하지 않는다. 즉, 1번에서 바로 2번으로 가는 것이 1->4를 거쳐 2번으로 가는 길보다 더 적게 걸린단 뜻이다.

다음으로 선택될 노드는 아직 방문하지 않은 노드 2, 3, 5, 6 중 거리값이 가장 작은 노드이므로 2 또는 5이다. 거리 값이 같다면 일단 인덱스가 작은 노드를 택한다고 하고 2번으로 가보자.

2번 노드와 연결된 3, 4번 노드에 대해 같은 과정을 반복한다.

그 다음 노드는 3, 5, 6번 중 가장 거리값이 작은 5번 노드가 되겠다.

5번 노드와 연결된 6번 노드에 같은 과정을 반복한다.

다음 노드를 선택해야 하는데, 아직 방문하지 않은 3번과 6번 중 거리값이 작은 것은 6번이다. 그런데 6번은 더 이어지는 노드도 없는데다 도착 노드이다. 따라서 알고리즘을 종료한다.

최종적으로는 1번에서 6번까지 오는 데 1 - 4 - 5 - 6의 경로를 거치고 최소 거리는 4가 된다.

1-4. 특징

위 동작 예시에서 볼 수 있듯이, 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다.

또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다.

도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.

다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다는 중요한 특징이 있다.

 

위 그림의 상황에서 1 → 4의 경로가 최단경로이려면 3+k가 1보다 커야 한다. 즉, k > -2가 성립해야 한다. 반대로 k가 -5라고 한다면 오히려 1 → 2 → 4 경로가 더 최단 경로가 된다. 그 말인 즉, 1번에서 연결된 노드 중 4번이 가중치가 적다는 이유로 최단 거리를 1이라 할 수는 없다는 이야기이다.

따라서 다익스트라 알고리즘을 사용하기 위해서는 정점 사이를 잇는 간선의 가중치가 양수여야 한다. 그래야 한 번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 되는 것이다.

1-5. 구현 방법

다익스트라 알고리즘을 구현하는 방법에는 '방문하지 않은 노드'를 다루는 방식에서 '순차 탐색'을 할 것이나 '우선순위 큐'를 쓸 것이냐로 나뉜다. 자세한 방식은 아래에서 계속한다.

---

2. 구현(1): 순차 탐색

'방문하지 않은 노드 중 거리값이 가장 작은 노드'를 선택해 다음 탐색 노드로 삼는다. 그 노드를 찾는 방식이 순차 탐색이 된다. 즉 거리 테이블의 앞에서부터 찾아내야 하므로 노드의 개수만큼 순차 탐색을 수행해야 한다. 따라서 노드 개수가 N이라고 할 때 각 노드마다 최소 거리값을 갖는 노드를 선택해야 하는 순차 탐색이 수행되므로 (N−1)×N=O(*N^*2)의 시간이 걸린다.

아래 코드에서 dist[]는 각 노드까지의 최소 거리를 저저장하고, visited[]는 방문 여부를, map[][]은 한 노드에서 다른 노드로의 거리를 저장하고 있다.

#include <vector>
#include <queue>
// 아직 방문하지 않은 노드 중
// 가장 거리값이 작은 노드의 인덱스 반환
int FindSmallestNode()
{
	int min_dist = INF;
    int min_idx = -1;
    for (int i = 0; i<= N; i++)
    {
    	  if (visited[i] == true)
        	continue;
        if (dist[i] < min_dist)
        {
        	  min_dist = dist[i];
            min_idx = i;
        }
    }
    return min_idx;
}

// 다익스트라
void Dijkstra()
{
	for (int i = 1; i <= N; i++)
    dist[i] = map[start][i];  // 시작 노드와 인접한 정점에 대해 거리 계산

    dist[start] = 0;
    visited[start] = true;

    for (int i = 0; i < N - 1; i++)
    {
    	  int new_node = FindSmallestNode();
        visited[new_node] = true;

        for(int j = 0; j <= N; j++)
        {
        	  if (visited[j] == true)
            	continue;
            if (dist[j] > dist[new_node] + map[new_node][j])
            	dist[j] = dist[new_node] + map[new_node][j];
        }
    }
}

3. 구현(2): 우선순위 큐

3-1. 특징

순차 탐색을 사용할 경우 노드 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다. 이를 개선하기 위해 우선순위 큐를 도입하기도 한다.

거리 값을 담을 우선순위 큐는 힙으로 구현하고, 만약 최소 힙으로 구현한다면 매번 루트 노드가 최소 거리를 가지는 노드가 될 것이다.

파이썬의 경우 PriorityQueue나 heapq 라이브러리로 우선순위 큐, 최소 힙이 지원되며, C++의 경우 <queue> 라이브러리에서 최대 힙을 지원하는 priority_queue 를 사용할 수 있다. 최대 힙을 최소 힙으로 쓰려면 저장되는 값에 -를 붙여 음수로 만들면 된다.

우선순위 큐에서 사용할 '우선순위'의 기준은 '시작 노드로부터 가장 가까운 노드'가 된다. 따라서 큐의 정렬은 최단 거리인 노드를 기준으로 최단 거리를 가지는 노드를 앞에 배치한다.

위의 순차 탐색을 쓰는 구현과는 다르게 우선순위 큐를 사용하면 방문 여부를 기록할 배열은 없어도 된다. 우선순위 큐가 알아서 최단 거리의 노드를 앞으로 정렬하므로 기존 최단 거리보다 크다면 무시하면 그만이다. 만약 기존 최단거리보다 더 작은 값을 가지는 노드가 있다면 그 노드와 거리를 우선순위 큐에 넣는다. 우선순위 큐에 삽입되는 형태는 <거리, 노드> 꼴이다.

3-2. 동작 예시

출발 노드인 1번의 거리를 업데이트하고 우선순위 큐에 넣는다.

큐에서 맨 앞 노드인 <거리 0, 노드 1>을 꺼내 그 인접 노드를 조사한다. 거리값이 업데이트 되는 노드만, 즉 최소 거리로 업데이트 되는 노드만 큐에 넣는다. 큐는 거리값이 작은 순서대로 정렬된다.

<거리 1, 노드 4>를 꺼내 그 인접 노드를 조사한다. 최소 거리로 거리가 업데이트 된 5번을 큐에 넣는다. 2번의 경우 기존의 거리값인 2보다 1 + 2 = 3이 더 크므로 2번은 큐에 넣지 않는다.

같은 과정의 반복으로 <거리 2, 노드 2>의 인접 노드를 조사하고 거리값이 갱신된 노드만 큐에 넣는다. 3번이 큐에 들어간다.

큐가 빌 때까지 해당 과정을 반복한다.

최종적으로 도착 노드의 거리 값이 최소 거리가 된다.

그래프의 형태는 '시작 노드 / 끝 노드 / 그 사이 간선의 가중치'를 입력 받아 인접 행렬 graph[][]에 넣어 표현한다.

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

# define INF 99999999

// 시작 위치와 정점의 개수, 인접 행렬을 받아
// 최소 거리 행렬을 반환함
vector<int> dijkstra(int start, int N, vector<pair<int, int>> graph[])
{
    vector<int> dist(N, INF);  // 거리를 저장할 리스트 초기화
    priority_queue<pair<int, int>> pq;  // 우선순위 큐 선언

    dist[start] = 0;  // 시작 노드 거리를 0으로 함
    pq.push({ 0, start });  // 우선순위 큐에 넣기

    while (!pq.empty())
    {
        int cur_dist = -pq.top().first; // 큐에서 꺼내 방문하고 있는 정점의 거리
        int cur_node = pq.top().second;  // 정점의 인덱스(번호)
        pq.pop();

        for (int i = 0; i < graph[cur_node].size(); i++)
        {
            int nxt_node = graph[cur_node][i].first;  // 인접 정점 번호
            int nxt_dist = cur_dist + graph[cur_node][i].second;  // 인접 정점까지 거리

            if (nxt_dist < dist[nxt_node])  // 지금 계산한 것이 기존 거리값보다 작다면
            {
                dist[nxt_node] = nxt_dist;  // 거리값 업데이트
                pq.push({ -nxt_dist, nxt_node });  // 우선순위 큐에 넣기
            }
        }
    }

    return dist;  // start 노드로부터 각 노드까지 최단거리를 담은 벡터 리턴
}

int main()
{
    const int N = 10;  // 노드의 개수가 10개라 가정.
    int E = 20;  // 간선의 개수가 20개라 가정.
    vector<pair<int, int>> graph[N];  // 그래프 형태 선언

    for (int i = 0; i < E; i++)
    {
        int from, to, cost;  // 간선의 시작점, 끝점, 가중치
        cin >> from >> to >> cost;
        graph[from].push_back({ to, cost });  // 무향 그래프라 가정하므로 시작점과 끝점 둘 다 벡터에 넣어야 함
        graph[to].push_back({ from, cost });
    }

    vector<int> dist = dijkstra(0, N, graph);

    cout << "끝점까지의 최단거리" << dist[N - 1] << endl;

    return 0;
}

3-4. 시간 복잡도

간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 O(E logV)가 된다.

우선순위 큐에서 꺼낸 노드는 연결된 노드만 탐색하므로 최악의 경우라도 총 간선 수인 E만큼만 반복한다.

이때 각 간선에 대해 우선순위 큐에 새로운 거리 값을 삽입하게 되는데, 이 삽입 연산의 시간 복잡도가 O(log⁡N)이다.

즉 하나의 간선에 대해서는 O(logE)이고 모든 간선을 우선순위 큐에 넣고 뺀다고 했을 때 O(ElogE) 시간이 걸린다.

O(logE)는 *V^2(모든 노드가 연결되어 있는 경우 V(V-1))보다 항상 작기 때문에 logE < 2logV이므로 O(logV)으로 표현할 수 있다.

E개의 간선을 우선순위 큐에 넣었다 빼는 최악의 경우에 대해서는 O(E logV)이다.

0 - 1 bfs

가중치가 0과 1로 이루어진 그래프에서는 다익스트라 알고리즘보다 0-1 BFS가 더 빠르게 동작한다. 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이지만 0-1 BFS는 O(V+E)의 시간 복잡도를 가지기 때문이다.

원리

• deque front에서 현재 노드를 꺼낸다.
• 인접 노드를 체크한다.
• 현재 노드까지의 비용 + 인접 노드로의 비용 < 인접 노드까지 소요된 비용의 경우 노드로의 비용을 갱신한다.
• 인접 노드로의 가중치가 0이라면 deque의 front에 삽입, 1이라면 deque의 back에 삽입한다.
• deque가 empty가 될 때까지 위 과정을 반복한다.

시간 복잡도

비용이 적은 경로부터 탐색하기 때문에 특정 간선을 2번 초과하여 지나가는 경우는 없다. 이와 같은 의미에서 같은 정점 역시 2번을 초과하여 방문하지 않기 때문에 deque의 크기는 최대 V가 된다.

따라서 O(V) + O(E) = O(V+E)가 된다.

다시 본론으로 돌아와서

• 우선 순위 큐 다익스트라 알고리즘
• 0 - 1 bfs 알고리즘

이렇게 두 가지로 숨바꼭질 문제를 풀어볼 것이다.

우선 순위 큐 다익스트라

#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321
#define MAX 100001
using namespace std;

// 거리와 노드 정보 필요 

void Solve(int start, int end)
{
    // 거리를 저장할 배열
    vector<int> dist(MAX, INF);

    // 우선 순위 큐를 이용한 다익스트라 알고리즘 구현
    // 거리 & 인덱스
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push(make_pair(0, start));
    dist[start] = 0;

    while (!pq.empty())
    {
        int curDist = pq.top().first;
        int curIndex = pq.top().second;
        pq.pop();

        if (curIndex == end)
        {
            cout << dist[end];
            return;
        }
        // 이미 처리된 노드라면 건너뛰기
        // curDist는 오래된 값이라고 보면 된다. (우선순위 큐의 원리)
        // dist[curIndex]는 최소값을 반영한 최신값 
        if (curDist > dist[curIndex]) continue;
        
        for (int dx : {curIndex - 1, curIndex + 1, curIndex * 2})
        {
            if (dx < 0 || dx >= MAX) continue;
            
            int nextDist = curDist + (dx == curIndex * 2 ? 0 : 1);
            
            if (nextDist < dist[dx])
            {
                dist[dx] = nextDist;
                pq.push({nextDist, dx});
            }
        }
    }
}

int main()
{
    int N, K;
    cin >> N >> K;

    Solve(N, K);
}

몰랐던 점

1. 우선순위 큐 최소 힙 선언

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

• 음수를 붙이지 않고도 이렇게 선언할 수 있다.

1. 우선 순위 큐에 push할 때 pair의 순서가 중요

pq.push(make_pair(0, start));

• 처음엔 인덱스를 먼저 넣어 최소 거리가 매번 큐의 front에 있는 걸 보장하지 못했다.
• 우선순위 큐는 pair 자료형을 사용 할 때 첫 번째 인자 기준으로 먼저 정렬하고, 같다면 두 번째 인자 기준으로 정렬한다.

1. 이미 최소값을 찾은 인덱스를 구별

// 이미 처리된 노드라면 건너뛰기
// curDist는 오래된 값이라고 보면 된다. (우선순위 큐의 원리)
// dist[curIndex]는 최소값을 반영한 최신값 
if (curDist > dist[curIndex]) continue;

• curDist는 큐에 있었던 값이므로 오래된 값이다.
• 다익스트라 알고리즘 구조상 최단 거리가 나오면 최신 사항에 반영하므로 오래된 값은 최신 값보다 클 수밖에 없다.
• 이것을 이용해 거른다.

0 -1 bfs

#include <iostream>
#include <deque>
#include <vector>
#define INF 987654321
#define MAX 200001
using namespace std;

// 거리와 노드 정보 필요 

void Solve(int start, int end)
{
    // 거리를 저장할 배열
    vector<int> dist(MAX, INF);

    // deque을 이용한 0-1 bfs 구현
    // 거리 & 인덱스
    deque<pair<int, int>> dq;
    dq.push_back(make_pair(0, start));
    dist[start] = 0;

    while (!dq.empty())
    {
        int curDist = dq.front().first;
        int curIndex = dq.front().second;
        dq.pop_front();

        if (curIndex == end)
        {
            cout << dist[end];
            return;
        }
        
        for (int dx : {curIndex - 1, curIndex + 1, curIndex * 2})
        {
            if (dx < 0 || dx >= MAX) continue;
            
            int nextDist = (dx == curIndex * 2) ? curDist : curDist + 1;
            
            if (nextDist < dist[dx])
            {
                dist[dx] = nextDist;
                if (dx == curIndex * 2)
                    dq.push_front({nextDist, dx});
                else
                    dq.push_back({nextDist, dx});
            }
        }
    }
}

int main()
{
    int N, K;
    cin >> N >> K;

    Solve(N, K);
}

시간이 다익스트라보다 짧은 것을 확인할 수 있다!

다익스트라와 다른 점

if (nextDist < dist[dx])
{
    dist[dx] = nextDist;
    if (dx == curIndex * 2)
        dq.push_front({nextDist, dx});
     else
        dq.push_back({nextDist, dx});
}

최소 거리를 찾아 거리를 갱신할 때, 가중치가 0이면 deque front에 push하고, 가중치가 1이면 deque back에 push하는 부분만 다르다.

다익스트라는 0인지 1인지 상관없이 바로 우선순위 큐에 넣는다.

---

참고 블로그

[알고리즘] 다익스트라(Dijkstra) 알고리즘