[백준] 13549번 : 숨바꼭질 3

문제

 

---

풀이

 

myunji.tistory.com/287?category=1154147

[백준] 1697번 : 숨바꼭질

이 문제의 응용버전이다.

 

순간이동과 앞뒤 이동 모두 1초가 걸렸던 1697번과 달리 이번엔 순간이동을 0초만에 할 수 있다.

즉 각 이동에 대한 가중치가 달라진 것인데, 그래프의 관점에서 말하자면 간선에 가중치가 생긴 것이다.

 

이런 경우에서 최단거리를 찾고자 한다면 가중치가 작은 것을 우선으로 탐색해야 한다. 괜히 가중치 0으로 갈 수 있는 곳을 가중치 1로 가버려 visited 처리 해버리면 그만큼의 거리를 손해보기 때문이다.

 

보통 이런 문제는 우선순위 큐를 이용해 다익스트라로 풀지만 이 문제는 가중치가 0과 1뿐이다.

이런걸 0-1 너비 우선 탐색이라고 부르는데 이건 덱으로 구현하는게 편하다.

 

순간이동으로 갈 수 있는 경우엔 덱의 앞에 삽입하고, 나머지 이동은 덱의 뒤에 삽입한다.

그럼 순간이동으로 갈 수 있는 경로를 먼저 탐색하게 될 것이다.

---

소스코드

 

#include <iostream>
#include <deque>

using namespace std;

const int MAX = 100000;
int pos[MAX + 1];
deque<int> dq;

void bfsPromising(int source, int dest, int flag) {
    if ((dest >= 0) && (dest <= MAX) && (pos[dest] == 0)) { //방문한 적 없는 좌표
        if (flag) {
            pos[dest] = pos[source]; //여기까지 오는데 걸리는 최소 시간
            dq.push_front(dest); //앞에 삽입
        }
        else {
            pos[dest] = pos[source] + 1; //여기까지 오는데 걸리는 최소 시간
            dq.push_back(dest); //뒤에 삽입
        }
    }
}

int bfs(int start, int end) {
    dq.push_back(start);
    while (!dq.empty()) { //도착지점 방문하면 반복 종료
        int cur = dq.front();
        dq.pop_front();
        if (cur == end)
            return pos[end] - 1;
        //순서 중요
        bfsPromising(cur, cur * 2, 1); //X*2
        bfsPromising(cur, cur + 1, 0); //X+1
        bfsPromising(cur, cur - 1, 0); //X-1
    }
    return 0;
}

int main() {
    int N, K;

    cin >> N >> K;
    pos[N] = 1; //시작점 방문 표시
    cout << bfs(N, K);
}

1697번의 코드에서 큐를 덱으로 바꾸고 약간의 우선순위 처리를 해줬다.

그 부분만 살펴보도록 하겠다.

 

        //순서 중요
        bfsPromising(cur, cur * 2, 1); //X*2
        bfsPromising(cur, cur + 1, 0); //X+1
        bfsPromising(cur, cur - 1, 0); //X-1

bfs 탐색 가능의 조건을 체크하는 순서가 중요해졌다.

예를 들어 N=1, K=2일 때 X+1의 조건을 먼저 확인하면 1초라는 결과가 나올 것이다.

하지만 1*2=2이기 때문에 최단 경로는 순간이동을 통해 가는 0초이다.

 

즉, X+1의 결과와 X*2의 결과가 같을 때 X*2에 더 우선권을 부여하기 위해 X*2를 먼저 탐색한다.

 

void bfsPromising(int source, int dest, int flag) {
    if ((dest >= 0) && (dest <= MAX) && (pos[dest] == 0)) { //방문한 적 없는 좌표
        if (flag) {
            pos[dest] = pos[source]; //여기까지 오는데 걸리는 최소 시간
            dq.push_front(dest); //앞에 삽입
        }
        else {
            pos[dest] = pos[source] + 1; //여기까지 오는데 걸리는 최소 시간
            dq.push_back(dest); //뒤에 삽입
        }
    }
}

bfsPromising 함수에는 flag인자를 추가하여 순간이동과 그냥 이동을 구분했다.

순간이동은 덱의 앞에 삽입하고 그냥 이동은 뒤에 삽입하여 순간이동이 먼저 처리되도록 했다.