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

 

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

 

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

---

 

해결전략

 

너비우선탐색 BFS

 

 

---

 

정답코드

 

#include <iostream>  
#include <vector>    
#include <queue>     
using namespace std;

int N, K; // N: 수빈이의 현재 위치, K: 동생이 있는 위치
int minTime = 2147000000, num;  // 최소 시간, 방법의 수
vector<int> ch(100001, -1);  // 위치에 따른 시간을 저장할 벡터. 초기값은 -1

int main() {
	ios::sync_with_stdio(false);  
	cin.tie(0); cout.tie(0);  

	cin >> N >> K;  /
	
	queue<int> Q;  
	Q.push(N);  
	ch[N] = 1; 

	while (!Q.empty()) 
	{
		int x = Q.front(); 
		Q.pop();  

		if (ch[x] > minTime) continue;  // 현재 위치의 시간이 최소 시간보다 크면 무시

		if (x == K) {  // 현재 위치가 동생의 위치라면
			if (ch[x] < minTime) {  // 현재 위치의 시간이 최소 시간보다 작다면
				minTime = ch[x];  // 최소 시간 업데이트
				num = 0;  // 방법의 수 초기화
			}
			num++;  // 해당 시간에 도달하는 방법의 수 증가
		}

		// 가능한 이동: x-1, x+1, x*2
		// 각 이동에 대해, 이동한 위치가 유효하고, 아직 방문하지 않았거나(ch[] == -1) 이전에 방문했더라도 현재 시간보다 클 경우(ch[] == ch[x] + 1)에만 큐에 추가하고 시간 업데이트
		if (x - 1 >= 0 && (ch[x - 1] == -1 || ch[x - 1] == ch[x] + 1)) {
			Q.push(x - 1);
			ch[x - 1] = ch[x] + 1;
		}
		if (x + 1 <= 100000 && (ch[x + 1] == -1 || ch[x + 1] == ch[x] + 1)) {
			Q.push(x + 1);
			ch[x + 1] = ch[x] + 1;
		}
		if (x * 2 <= 100000 && (ch[x * 2] == -1 || ch[x * 2] == ch[x] + 1)) {
			Q.push(x * 2);
			ch[x * 2] = ch[x] + 1;
		}
	}

	cout << minTime-1 << "\n";  // 최소 시간 출력
	cout << num << "\n";  // 방법의 수 출력

	return 0;
}

 

 

 

---