[백준] 13549번 숨바꼭질 3 C++ 풀이

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• BFS
• 최단 경로 탐색
• 다익스트라
• 0-1 BFS

---

문제 설명

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

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

---

입력 설명

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

 

---

출력 설명

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

---

예제 입력

5 17

---

예제 출력

2

---

아이디어

BFS를 돌리는데 n==k일 때 바로 t를 출력하는 것이 아니라 최소 시간을 찾기 위해서 queue가 empty가 될 때까지 탐색한 후 출력한다.

---

알고리즘

arr에 현재까지 걸린 시간을 저장하는데 현재까지 걸린 시간이 arr에 저장된 시간보다 짧은 경우에만 저장한다.

즉, 현재 방문하고 있는 경우가 최단 시간이 될 가능성이 있는 경우에만 저장한다.

이를 BFS로 반복하며 queue가 empty가 될 때까지 반복한 후 arr[k]를 출력한다.

---

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    vector<int> arr(100001,100001);
    queue<pair<int,int>> q;
	int n, k;
	cin>>n>>k;
	q.push({n,0});
	while(!q.empty())
	{
		int x = q.front().first;
		int t = q.front().second;
        q.pop();
		if(t < arr[x]) arr[x] = t;
		if(0 <= x-1 && t+1 < arr[x-1]) q.push({x-1,t+1});
		if(x+1 <= 100000 && t+1 < arr[x+1]) q.push({x+1,t+1});
		if(x*2 <= 100000 && t < arr[x*2]) q.push({x*2,t});
	}
	cout<<arr[k];
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/13549

항상 n <= k이 아닐 수도 있다는 점과

시간의 가중치가 0 또는 1이라는 점을 잘 유의해서 푼다면 간단한게 풀 수 있는 문제였다.

다만 우선순위큐를 사용하는 0-1 BFS를 이용해서도 풀 수 있는 문제였는데 그 방법은 사용하지 못했다.

다음에 또 숨바꼭질 문제를 푼다면 이러한 방법도 사용해서 풀어보고 싶다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!