[BOJ] 13549번 : 숨바꼭질3 (C++)

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

13549번: 숨바꼭질 3

 

이 문제는 숨바꼭질 문제를 풀고 나서 푸는 것을 추천한다. 

숨바꼭질와 숨바꼭질3 문제에서의 차이는 순간이동을 할 때 시간이 걸리지 않는다는 것이다. 

순간이동이 0초가 되면, 순간이동과 걷는 것 중 우선순위가 생기기 때문이다. 

BFS는 모든 간선의 가중치가 동일해야 한다는 전제조건이 필요한데, 이 문제는 가중치가 달라지게 되었다. 

그래서 일반 BFS처럼 풀면 안되고 다른 방법으로 해결해야 한다. 

 

1. 다익스트라 알고리즘

2. 0-1 BFS 알고리즘, 가중치가 0인 간선에 연결된 정점은 큐에 맨 뒤가 아닌 맨 앞에 넣는다. (2번 방법 코드)

3. *2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱배인 좌표들을 전부 큐에 넣는 방법 (3번 방법 코드)

 

 

이 중에서 숨바꼭질 문제와 해결방법이 제일 비슷한 2번 문제로 해결하였다.

가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다. 

#include <iostream>
#include <deque>
using namespace std;
const int MX = 100000+2;

int n,k;
int dist[MX];
deque<int> dq;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>k;

    fill(dist,dist+MX, -1); //-1로 초기화

    dist[n]=0; //n에서 출발
    dq.push_back(n);

    while(!dq.empty()){
        auto cur = dq.front(); dq.pop_front();
        if(cur==k) {
            cout<<dist[cur];
            return 0;
        }

        for(auto i : {cur-1, cur+1, cur*2}){
            if(i<0||i>MX) continue; //범위를 벗어남
            if(dist[i]!=-1) continue; //이미 방문함

            if(i==cur*2){ //*2인 경우는 덱의 앞에 넣음(우선순위 높음)
                dist[i] = dist[cur];
                dq.push_front(i);
            }
            else{
                dist[i] = dist[cur]+1;
                dq.push_back(i);
            } 
        }
    }
    return 0;
}

 

 

참고)

https://jdselectron.tistory.com/58 

 

 

느낀점)

숨바꼭질1을 이미 풀어본 상태에서 마주한 문제라 크게 어렵지 않다고 생각하였다. 

풀이방법 중 1.다익스트라는 다익스트라를 공부하고 다시 봐야겠다. 

3번 풀이법도 이해가 안가서 일단 스킵했는데 공부하면 좋을 것 같다. 

0-1 BFS는 처음 접하였는데, 굉장히 유용한 것 같다. (0-1BFS 내용 레퍼런스) 

 

간단히 말하자면 0-1 BFS란, 가중치가 0과 1로만 주어진 특수한 그래프에서 최단 경로를 찾고자 할 때인 특수한 환경에서 작동할 수 있는 BFS이다. 최단 경로는 다익스트라가 베스트가 아니란 것인가? 적어도 이 그래프에서는 아니다. 보편적으로 사용하는 다익스트라 알고리즘의 시간복잡도가 O(ElogE) 혹은 O(ElogV)인데 0-1 BFS를 사용하면 단지 O(V+E)의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다.