[백준 13549, c++] 숨바꼭질3(bfs, deque, priority_queue)

문제 번호

• 13549(https://www.acmicpc.net/problem/13549)

문제 및 입/출력

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

 

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

예제 입력1

5 17

예제 출력1

2

 

문제 풀이

N부터 K까지 이동하는데에 걸리는 최소 시간 t를 구하는 문제이다. 이전에 풀었던 숨바꼭질 1(1697) 문제에서 약간 변형한 문제이다. 이동 방법은 총 3가지가 존재하고, 각각 방법의 이동시간에 차이가 있다. 순간 이동(2*X)은 0초가 걸리며 걷는 이동(X+1, X-1) 이동은 각각 1초가 걸린다.

 

• 순간 이동(0초 소요)은 걷는 이동(1초 소요)보다 더 빠르기때문에, 우선 순위가 높다.
• 이 문제는 단순한 BFS를 요구하는 문제가 아니다. 왜냐하면 BFS는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다.
• 그렇기 때문에 이 문제는 다음과 같은 방법들을 사용하여 해결할 수 있다.
  • 다익스트라 알고리즘
  • 0s/1s BFS 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법
  • * 2를 별도의 간선으로 생각하지 않고, +1이나 -1에 의한 좌표를 큐에 넣을 때 그 좌표의 2의 거듭제곱 배인 좌표들을 전부 큐에 넣는 방법

나는 이러한 문제를 deque과 priority_queue 를 사용하여 "0s/1s BFS 가중치가 0인 간선에 연결된 정점은 큐의 맨 뒤가 아닌 맨 앞에 넣는 방법"으로 풀이해보았다.

 

#덱(deque) 이란?

양쪽에서 끝나는 큐(Double Ended Queue)로 <deque>에 정의되어 있다. 흔히 줄여서 덱("deck")으로 발음한다. 보통 queue의 경우에는 한쪽에서는 삽입이 일어나고, 반대쪽에서는 삭제가 일어나지만, 그 반대가 되는 기능을 할 수는 없다. (FIFO)
또한 stack의 경우에는 top에서 삽입(push)와 삭제(pop)가 일어나고 end에서는 아무것도 할 수 없다.(LIFO)

deque의 경우에는 queue와 stack을 합친것이라 볼 수 있으며, 즉, 양쪽 끝에서 삽입(push)와 삭제(pop) 모두 수행할 수 있게된다.

• 순간 이동을 할 경우 해당 좌표는 덱의 앞에 넣는다.
• 걷는 이동을 할 경우 해당 좌표는 덱의 뒤에 넣는다.
• 좌표를 덱에서 꺼낼 때, 덱의 앞에서부터 꺼내오는 pop_front()를 사용하므로 순간이동의 우선순위를 높게 처리할 수 있다.

---

우선순위 큐란?

기존 큐는 FIFO(First-In-First-Out)의 선입선출 구조를 띄고있다. 하지만 우선순위 큐는 기존 큐와는 다르게 넣는 건 동일하되, 빠지는 건 최소, 혹은 최대부터 빠지게 된다. 여기서 최대부터 빠지는 걸 Max Heap 이라 칭하고, 최소부터 빠지는 걸 Min Heap이라고 칭한다.

선언은 아래와 같이 한다.

# 우선순위를 오름차순으로 설정
priority_queue<int> q;
priority_queue<int, vector<int>,less<int> > q;

# 우선순위를 내림차순으로 설정
priority_queue<int, vector<int>,greater<int> > q;

소스 코드

# 덱(deque)을 이용한 풀이

#include <iostream>
#include <deque>
#include <stdio.h>
#include <cstring> // memset
 
using namespace std;
 
#define MAX_SIZE 100000+1
 
int N, K;
int visited[MAX_SIZE];
 
int bfs() {
    deque<int> dq;
    dq.push_back(N);
    visited[N] = 1;
    while (!dq.empty()) {
         // 덱의 앞의 요소들부터 꺼내옴
        int pos_x = dq.front();
        dq.pop_front();
 
        if(pos_x == K) return visited[K] - 1;
 
        // 순간이동은 덱의 앞쪽에 집어넣음.
        if (pos_x * 2 < MAX_SIZE && !visited[pos_x * 2]) {
            dq.push_front(pos_x * 2);
            visited[pos_x * 2] = visited[pos_x];
        }
 
        // 걷는이동은 덱의 뒤쪽에 집어넣음.
        if (pos_x + 1 < MAX_SIZE && !visited[pos_x + 1]) {
            dq.push_back(pos_x + 1);
            visited[pos_x + 1] = visited[pos_x] + 1;
        }
 
        // 걷는이동은 덱의 뒤쪽에 집어넣음.
        if (pos_x - 1 >= 0 && !visited[pos_x - 1]) {
            dq.push_back(pos_x - 1);
            visited[pos_x - 1] = visited[pos_x] + 1;
        }
    }
}
 
int main() {
    scanf("%d %d", &N, &K);
    printf("%d\n", bfs());
    return 0;
}
 

-----

# 우선순위 큐(priority_queue) 풀이

#include <iostream>
#include <queue>
#include <stdio.h>
#include <cstring> // memset
 
using namespace std;
 
#define MAX_SIZE 100000+1
 
int N, K;
bool visited[MAX_SIZE];
 
int bfs() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({ 0, N });
    visited[N] = true;
    while (!q.empty()) {
        int time = q.top().first;
        int x = q.top().second;
        q.pop();
 
        if (x == K) return time;
 
        if (x * 2 < MAX_SIZE && !visited[x * 2]) {
            q.push({ time, x * 2 });
            visited[x * 2] = true;
        }
 
        if (x + 1 < MAX_SIZE && !visited[x + 1]) {
            q.push({ time + 1, x + 1 });
            visited[x + 1] = true;
        }
 
        if (x - 1 >= 0 && !visited[x - 1]) {
            q.push({ time + 1 , x - 1 });
            visited[x - 1] = true;
        }
    }
}
 
int main() {
    scanf("%d %d", &N, &K);
    printf("%d\n", bfs());
    return 0;
}