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

#문제

13549번: 숨바꼭질 3
https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

---

#접근방법

이 문제는 숨바꼭질 2에서 변형된 문제이다. https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-12851%EB%B2%88-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-2-CC

[백준] 12851번 : 숨바꼭질 2 [C/C++]

숨바꼭질 2는 x-1, x+1, x*2로 이동할 때, 모두 1초가 소모가 되지만, 숨바꼭질 3는 x-1, x+1은 1초가 소모되고 x*2로 이동할 때 0초가 소모가 된다는 것이 다르다.
 
숨바꼭질 2는 queue를 이용한 bfs로 접근이 가능하지만, 숨바꼭질 3는 0초가 소모가 되는 이동법이 있으므로 우선순위 큐인 priority_queue를 사용해야된다.

반응형

---

#풀이

#include <stdio.h>
#include <queue>
using namespace std;

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
bool visit[100005];

int main(){
	int n,k;
	
	scanf("%d %d",&n,&k);
	
	pq.push(make_pair(0,n));
	
	while(!pq.empty()){
		int time = pq.top().first;
		int x = pq.top().second;
		pq.pop();
		
		visit[x] = 1;
		
		if(x==k){
			printf("%d",time);
			break;
		}
		
		if(x-1>=0 && !visit[x-1])
			pq.push(make_pair(time+1,x-1));
		if(x+1<=100000 && !visit[x+1])
			pq.push(make_pair(time+1,x+1));
		if(x*2<=100000 && !visit[x*2])
			pq.push(make_pair(time,x*2));
	}
	
	return 0;
}

위에 설명한 것과 같이 priority_queue를 사용해야 이동한 시간이 가장 빠른 것을 찾을 수 있다. 우선순위 큐는 기본적으로 내림차순으로 정의가 되어있기 때문에
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
이렇게 써주면 오름차순으로 사용할 수 있다.
 
n,k를 입력받고 pq에 0,n을 넣어준다. pair로 구성된 우선순위큐는 제일 앞에있는 숫자를 기준으로 정렬을 한다. 따라서 시간과 위치를 넣을 때, 시간을 먼저 넣어줘야 우선순위 큐가 정상적으로 돌아간다.
 
while 반복문에 pq가 빌 때까지 반복하도록 조건을 설정하고 pq.top().first와 pq.top().second를 변수에 저장하고 pq.pop()를 해준다.
 
그리고 visit[x] = 1으로 이미 접근한 위치를 중복으로 접근하지 않도록 기록한다.
 
그리고 x-1, x+1로 이동할 때는 pq에 time+1을 넣고 x*2로 이동할 때는 time을 넣어준다.
 
이렇게 반복하다보면 x가 k에 무조건 도착하기 때문에 이때 time을 출력하고 반복문을 종료시켜준다.

---

#성능

---

#정리

bfs로 접근해서 풀어야 한다는 것,
 
x*2초 후에 이동하는 시간이 0초이기 때문에 우선순위 큐를 사용해야 한다는 것,
 
이미 방문한 곳을 중복하여 방문하지 않도록 하여 시간초과가 걸리게 하지 않는 것,
 
범위를 벗어나지 않도록 조건을 잘 작성하고 이를 구현할 수 있는 능력이 있으면 풀 수 있는 문제였다.