[백준] 12851 숨바꼭질 2(C++)

문제

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

 

문제 분석

해당 문제는 BFS 유형이다. 

 

왜 BFS인가?

처음에는 DP라고 생각을 했다. 이상하게 유독 BFS문제를 보면 DP라고 생각할 때가 종종 있는 것 같다...

 

하지만 이 문제가 BFS유형임에 확실한 것은 (물론 DP로도 풀려고하면 풀 수도 있겠지만) "가장 빠른 시간" 과 "가장 빠른 시간으로 찾는 방법" 이라는 키워드가 있기 때문이다.

 

가장 빠른 방법 중에서도 특히나 가중치가 없는 그래프의 경우에는 BFS임이 자명하다. 만약 가중치가 있을 경우에는 다익스트라 알고리즘을 사용해야한다.

 

특히나 트리일 경우에는, BFS는 반드시 "최단경로"를 거칠 수 밖에 없다. 왜냐하면, 해당 노드 간의 경로가 단방향, 또한 하나만 존재하기 때문에 어쩔 수 없다.

 

 

BFS가 트리에서 반드시 최단경로인 이유

1. 트리의 특성때문이다. 트리는 사이클이 없는 연결 그래프다. 따라서, 한 노드에서 다른 노드로 가는 경로는 유일하다. 
2. 레벨별로 탐색하기 때문이다. BFS는 시작노드로부터 가까운 노드부터 차례대로 탐색한다. 따라서 각 레벨의 노드들은 시작노드로부터 동일한 거리에 위치하고 있다. 따라서, 처음 BFS를 통해서 그 노드에 도달헀다면 그 노드는 최단경로를 통해 탐색한 것이다.
3. BFS는 한번 그 노드에 도달하면 그 노드를 다시 방문하지 않는다. 이는 BFS가 해당 노드까지의 최단 거리를 이미 찾았음을 의미하기 때문이다.

 

따라서 BFS는 트리에서 시작노드로부터 다른 모든 노드까지의 최단 경로를 보장하며, 이 속성으로 트리레벨에서 레벨 구조를 확인하거나 최단 경로를 찾을 때 BFS를 자주 사용한다.

 

 

다음으로, 이 문제에 대한 내용을 설명하자면, 수빈이가 N위치에 있을 때 동생이 있는 위치 K가 주어진다. 

위치의 범위는 둘다 0<=N,K<=100,000이다. 

 

+1, -1, *2를 행할 수 있고, 그때마다 1초가 지난다.

 

 

문제 풀이

+1, -1, *2를 행할 수 있고, 그때마다 1초가 지난다라는 조건에서, 3가지의 케이스가 모두 가중치가 1로 동일함을 알 수 있다. 모든 노드가 가중치가 1인 상태고, 이미 방문한 곳은 BFS특성상 이미 도착했다면 최단경로로 이미 도달했기 때문에 더 탐색할 가치가 없다. 따라서 모든 최단 거리 케이스를 그래프로 표현하면 트리형태가 될 것이다.

 

 

방문처리 & 레벨을 하나의 벡터로 처리한다.

 레벨과 방문처리는 하나의 vector를 통해서 충분히 해결할 수 있다. 

 

 메모리 제한이 512MB이기 때문에 적은 편이기도 하지만 vector를 고정크기배열로 100,001을 선언하고 해당 벡터에 방문 여부, 레벨

을 표현하면 된다. 0이면 방문하기 전인 것이고, 그렇지 않다면 방문한 것이니깐.

 

여기서 100,001인 이유는 최단경로중에 분명히 100,000까지 가는 방법 중 100,001에서 -1을 했을 때 최단경로일 수도 있기 때문이다. *2는 생각하지 않아도 된다. 

 

#define MAX_DISTANCE  100001

vector<int> road(MAX_DISTANCE, 0);

 

 레벨은 cost관점에서 이해하면 될것이다.

 

시작점에서 cost는 0이다. 그러나 그다음 트리로 가게 된다면 front노드를 보면 된다. front노드의 cost값이 0일테니, 자연스럽게 1이 될 것이고 같은 논리로 뻗어나갈 수 있다.

 

그렇다면 손쉽게 최단경로는 해결된다.

 

그런데 나는 트리의 특성에 대해서 잠시 잊고 있다가 난리가 났다. "당장은 도달하는데 늦었지만 최종적으로는 최단경로이지 않을까?"라는 굉장히 멍청한 생각이 머리에 가득차서 문제풀이하는데 해매게 됐다.

 

Queue의 사용

뭐 다른 문제와 다름없이 BFS는 큐를 쓴다. 

큐에는 현재 내 노드의 값을 쓴다. 그리고 앞에서 설명한 벡터에는 비용을 쓴다.

그렇게 되면 모든 것을 가질 수 있다. 현재 내 노드가 어떤 레벨인지도 알 수 있고 그 값이 무엇인지도 알 수 있게 된다.

 

그러면 이제는 어떨 때 큐에 넣으면 될지 고민만 하면 된다.

 

큐에 넣는 조건은 두 가진데 하나는 너무 당연하다.

1. 방문 하지 않았을 때.
2. 답을 찾았는데 내가 이전에 찾았던 답과 레벨이 같을 때.

답을 찾았는데 이전에 찾았던 답과 레벨이 같다는 말은, 곧 같은 레벨의 노드에서 답(K)가 나왔다는 것이다. 그러면 큐에 넣으면 된다. 그리고 답의 갯수를 올리면 되겠지.

 

답을 찾았다면 답을 저장하고있으면 되는것이다.

 

 

While문의 종단 조건

While문의 종단조건은 생각보다 간단했다.

탐색할 가치가 없는 순간에 대한 정의를 잘 세우면 된다. 바로 직관적으로 떠올릴 수 있다. 

답을 찾았을 때, 그때의 레벨보다 더 높아질 경우 탐색할 가치가 완전히 사라진다. 

 

따라서 종단조건은 매우 간단하다.

1. 큐가 텅 비었거나
2. 내가 탐색하고 있는 노드의 레벨이 답의 노드보다 더 높아졌을 때.

2번을 위해서 답의 기본값은 MAX로 둔다.

답이 MAX이하로 생길 경우 해당 조건이 잘 동작한다면 답의 다음 레벨에서 while이 중단될 것이다.

 

해당 코드는 +1, -1, *2에서 반복되기 때문에 메서드로 추출 해줬다.

void compareAndPush(int cost, int x){
    if (road[x] == 0 || road[x] == cost + 1) {
        road[x] = cost + 1;
        q.push(x);
    }

    if (x == K) {
        answerCount++;
        answer = cost;
    }
}

 

 

 

가장 내가 이번문제에 풀이하면서 가장 핵심적이었다 생각하는 부분은 "같은 레벨에 대한 처리"였다.

종단조건과 큐에 넣는 조건을 잘 판단해야한다는게 이번 문제의 어려운 점이었다고 생각한다.

 

최종 코드

#include <iostream>
#include <queue>
#define MAX_DISTANCE  100001
using namespace std;

int N, K;

queue<int> q;
vector<int> road(MAX_DISTANCE, 0);

int answer = MAX_DISTANCE;
int answerCount = 0;

void compareAndPush(int cost, int x){
    if (road[x] == 0 || road[x] == cost + 1) {
        road[x] = cost + 1;
        q.push(x);
    }

    if (x == K) {
        answerCount++;
        answer = cost;
    }
}

int main(){
    cin >> N >> K;
    if (N == K) cout << 0 << "\n" << 1 << endl;
    else {
        q.push(N);

        while (!q.empty()) {
            int front = q.front();
            int cost = road[front];

            if (cost > answer) break;
            if (front + 1 < MAX_DISTANCE) compareAndPush(cost, front + 1);
            if (front - 1 >= 0 ) compareAndPush(cost, front - 1);
            if (front * 2 < MAX_DISTANCE) compareAndPush(cost, front * 2);

            q.pop();
        }
        cout << answer + 1 << endl;
        cout << answerCount << endl;
    }
}