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

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

숨바꼭질 3의 경우는 1,2번 문제와 달리 순간이동을 하는데 걸리는 시간이 0초다.

 

이것을 잘 해결 하는 것이 매우 중요하다.

 

 

이 문제는 우선순위 큐(priority queue)를 활용하는 방법과 기본적인 큐를 활용해서 푸는 방법이 있다.

 

순간이동을 하는데 걸리는 시간이 0초이므로, 0초에 순간이동 하는 것을 큐에 먼저 삽입을 해줘야 한다.

 

우선순위 큐는 최대힙으로 구성되어있기 때문에, 최소힙으로 바꿔줘야한다.

• priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;    

 

 

기본적인 큐 소스코드

#include<bits/stdc++.h>
#define endl "\n"
#define MAX 100000+1
using namespace std;

int arr[MAX];
int move_time[3] = {0,1,1}; // x*2, x-1, x+1,  로 이동하는데 걸리는 시간
int answer = 0;
int n,k;
void bfs(int start)
{
    queue<pair<int, int>>q;    
    q.push({start,0});// 현재 위치 , 걸린 시간
    arr[start] = 0;
    while (!q.empty())
    {
        int pos = q.front().first;
        int t = q.front().second;
        q.pop();
        if(pos==k){
            answer = t;
            return;
        }
        for(int i=0; i<3; i++){
            int next_time = t+move_time[i];
            int next_pos=0;
            if(i==0) next_pos = pos*2;
            if(i==1) next_pos = pos-1;
            if(i==2) next_pos = pos+1;
            if(next_pos<0 || next_pos >MAX || arr[next_pos]!=-1)continue;
            if(next_pos==k){
                answer = next_time;
                return;
            }
            arr[next_pos] = next_time;
            q.push({next_pos, next_time});
            //cout<<"pos:"<<next_pos<<" time:"<<next_time<<endl;
        }
    }
    
}
int main() {	
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin>>n>>k;
    for(int i=0; i<MAX; i++){
        arr[i]=-1;
    }
    bfs(n);
    cout<<answer;


	return 0;
}

 

 

 

 

우선순위 큐 소스코드

#include<bits/stdc++.h>
#define endl "\n"
#define MAX 100000+1
using namespace std;

int arr[MAX];
int move_time[3] = {0,1,1}; // x*2, x-1, x+1,  로 이동하는데 걸리는 시간
int answer = 0;
int n,k;
void bfs(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;    
    pq.push({0,start});// 걸린 시간, 현재 위치
    arr[start] = 0;
    while (!pq.empty())
    {
        int t = pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        if(pos==k){
            answer = t;
            return;
        }
        for(int i=0; i<3; i++){
            int next_time = t + move_time[i];
            int next_pos=0;
            if(i==0) next_pos = pos*2;
            if(i==1) next_pos = pos-1;
            if(i==2) next_pos = pos+1;
            if(next_pos<0 || next_pos >MAX || arr[next_pos]!=-1)continue;
            if(next_pos==k){
                answer = next_time;
                return;
            }
            pq.push({next_time,next_pos});
            arr[next_pos] = next_time;
           // cout<<"pos:"<<next_pos<<" time:"<<next_time<<endl;
        }
    }
    
}
int main() {	
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin>>n>>k;
    for(int i=0; i<MAX; i++){
        arr[i]=-1;
    }
    bfs(n);
    cout<<answer;
	return 0;
}