13549번 - 숨바꼭질 3

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 13549번 - 숨바꼭질 3을 풀어보도록 하겠습니다.

 

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

 

 

[문제 접근]

저는 이 문제를 풀지 못했습니다. 정확히는 방향성을 잡지 못했습니다. 

항상 유형별 문제만 풀다가, 유형을 모르는 문제를 풀려고 하니까 방향성을 잡기가 어렵네요.

처음에는 그리디로도 생각했다가,, DP도 생각했는데, 정당성 그리고 점화식을 세울 수가 없더라구여.

1시간을 고민 끝에 결국 문제 관련 자료를 찾아보았고, 그래프와 관련된 문제라는 것을 알 수 있었습니다.

그래서 저는 BFS로 접근했고 풀어냈습니다!.

근데 이 문제를 BFS로 풀어서 맞춘 것은 순전히 우연이었습니다. 이 문제는 우리가 알고 있는 BFS를 단순히 사용해서는 풀리지 않는 문제이고 BFS 사용 목적 자체에도 부합하지 않는 문제입니다. BFS는 간선의 가중치가 같은 경우에 사용하는 알고리즘입니다.

이 문제는 간선의 가중치가 0 또는 1 입니다. 간선의 가중치가 다르기 때문에 엄밀히 BFS로 풀 수 없습니다.

그럼?? 뭐로 풀어야할까여?

간선의 가중치가 다를 때,  한 정점으로부터 모든 정점까지의 최단거리를 알수 있는 다익스트라 알고리즘으로 풀 수 있습니다.

그런데 여기서 응용 BFS 알고리즘을 알면 더 쉽고, 효율적으로 풀어낼 수 있습니다.

바로 0-1 BFS입니다. 가선의 가중치가 0 또는 1인 경우인 상황에서, Deque를 이용하여 가중치가 0인 경우는 deque의 front에 삽입하고, 가중치가 1인 경우는 deque의 back에 삽입하는 것입니다. 

이렇게 하면 모든 정점과 간선은 한 번씩만 방문하게 됩니다.

모든 간선은 deque에 최대 한 번씩만 front 혹은 back되므로 O(E),

최악의 경우 구하고자하는 정점이 가장 멀리있을때 모든 정점을 방문해야하므로  O(V)입니다.

그래서 O(V)+O(E)로 O(V+E) 시간복잡도를 가지게 됩니다.

우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도 O(ElogE)와 비교했을때 현저히 빠릅니다.

(혹은 단순 BFS를 사용하는데 가중치가 0인 간선을 먼저queue에 삽입해야 합니다)

(확인해보니 DP로도 풀수 있다고 한다 허걱 https://yeolife.tistory.com/41)

 

[풀이 전략]

- 0-1 BFS 풀이

 

[코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <deque>
using namespace std;


int dis[100001] ;
int const INF = 2147483647 ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int n, k ;
    cin >> n >> k;
    deque<int> dq ; // 1: 위치

    fill(dis,dis+100001, INF);
    dq.push_back(n);
    dis[n] = 0 ;
    while(!dq.empty()) {
        auto cur = dq.front() ; dq.pop_front();
        int x = cur;
        if(x < 0 || x > 100000) continue;
        if(x == k) break;
        
        if(x-1 >= 0 && dis[x-1] > dis[x]+1) { dq.push_back(x-1); dis[x-1] = dis[x]+1; }
        if(x+1 <= 100000 && dis[x+1] > dis[x]+1) {dq.push_back(x+1);  dis[x+1] = dis[x]+1; }
        if(2*x <= 100000 && dis[2*x] > dis[x]) {dq.push_front(2*x);  dis[2*x] = dis[x] ; }
    }

    cout << dis[k]; 
}

 

다익스트라 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;


int dis[100001] ;
int const INF = 2147483647 ;
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int n, k ;
    cin >> n >> k;
    
    fill(dis,dis+100001, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq ; // 최단거리 , 정점

    pq.push({0, n});
    dis[n] = 0 ;
    while (!pq.empty()) 
    {
        auto cur = pq.top() ; pq.pop();
        int d = cur.first;
        int v = cur.second;
        if(dis[v] != d) continue; // 다익스트라 알고리즘 킥.
        if(v-1 >= 0 && dis[v-1] > d + 1) { dis[v-1] = d+1; pq.push({d+1,v-1});}
        if(v+1 <= 100000 && dis[v+1] > d + 1) { dis[v+1] = d+1;  pq.push({d+1,v+1});}
        if(v*2 <= 100000 && dis[2*v] > d) { dis[2*v] = d ; pq.push({d,v*2});}
        
    }
    cout << dis[k]; 
}

 

[배울 점]

- 처음에 유형을 모르는 문제 풀 것.