백준 12851번 숨바꼭질 2

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/12851 

 

 

12851번: 숨바꼭질 2

 

 

이번 문제는 너비 우선 탐색(BFS) 문제였습니다.

 

 

 

《문제 풀이》

 

1. { N, 0 } 을 큐에 삽입 (0은 경과 시간)

2. 동생을 가장 빠른 시간으로 찾는 방법의 수를 구해야 하므로 pop 이후에 방문 체크 

3. 수빈이가 갈 수 있는 세 가지 위치가 범위에 충족되면 큐에 삽입

4. 최초로 동생 위치에 도달한 경우, 경과 시간을 result에 저장 후, cnt = 1

5. 이전에 동생 위치에 도달한 적이 있는 경우, cnt++

 

 

 

《C++ 코드》

 

#include <iostream>
#include <queue>
#define MAX 100001

using namespace std;

int cnt;
int result;
bool visited[MAX];

void hiding(int from, int to) {
	queue<pair<int, int>> q;
	q.push({from, 0});    
	visited[from] = true;
	
	while(!q.empty()) {
		int loc = q.front().first;
		int time = q.front().second;
		q.pop();
		
		visited[loc] = true;
		
		// 이전에 동생위치에 도달한적이 있는 경우  
		if(result == time && loc == to)
			cnt++;
		
		// 최초로 동생위치에 도달한 경우   
		if(!result && loc == to) {
			result = time;
			cnt = 1;
		}
		
		if(0 <= loc-1 && !visited[loc-1]) 
			q.push({loc-1, time+1});	
			
		if(loc+1 < MAX && !visited[loc+1]) 
			q.push({loc+1, time+1});
	
		if(loc*2 < MAX && !visited[loc*2]) 
			q.push({loc*2, time+1});   		
	}
}

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

	int N, K;
	cin>>N>>K;
	hiding(N, K);
	cout<<result<<"\n"<<cnt;
	
	return 0;
}

 

개발 환경: Dev-C++ 

 

 

 

baekjoon - 정답 화면