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

bfs를 활용해서 풀면된다. 

 

1. 수빈이와 동생의 위치가 처음부터 같을 경우 바로 결과값 출력 

2. 그렇지 않다면 수빈이의 x좌표값과 시간을 queue 넣고 bfs 호출 

3. 1초당 수빈이가 갈 수 있는 경우의 수는 총 3가지 이므로 방문하지 않거나 범위를 넘어서진 않는다면 queue에 push하고 bfs 호출 

4. 만약 수빈이의 위치가 처음으로 동생의 위치에 도달했을 때 시간 저장 

5. 같은 시간대에 도착한 경우가 여러개인 경우 result2 의 값을 증가 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std; 
queue<pair<int, int>>q;
int n, k;
int visited[100001]; 
int result1, result2; 
void bfs() {
	while (!q.empty()) {
		int x, time; 
		tie(x, time) = q.front(); 
		q.pop(); 
		visited[x] = 1; 
		if (result2 && x == k && result1==time )result2++; 
		if (!result2 && x == k) {
			result1 = time; 
			result2=1; 
		}
		if (x-1 >= 0 && !visited[x - 1])q.push({ x - 1, time + 1 });
		if (x+1 <= 100000 && !visited[x + 1])q.push({ x + 1, time + 1 });
		if (x * 2 <= 100000 && !visited[x * 2])q.push({ x * 2, time + 1 }); 
	}
}
int main() {	
	cin >> n >> k; 
	if (n == k) {
		cout << 0 << "\n" << 1; 
		return 0; 
	}
	q.push({ n,0 }); //0은 시간
	bfs(); 
	cout << result1 << "\n" << result2; 
}

 

12851번: 숨바꼭질 2