백준 13549번 숨바꼭질 3

 

 

 

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

 

 

13549번: 숨바꼭질 3

 

 

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

 

 

 

《문제 풀이》

 

1. 순간이동을 하는 경우에는 0초가 걸리므로 우선순위 큐를 이용하여 정렬 

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

3. 순간이동을 하는 경우가 경과 시간이 가장 짧으므로 해당 if 문을 가장 위에 작성

4. 큐에 삽입할 때 해당 위치의 visited 배열 true

5. 동생 위치에 도달하면 경과 시간 반환 

 

 

 

《C++ 코드》

 

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

using namespace std;

bool visited[MAX];

int hiding(int from, int to) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0, from}); // 경과시간이 짧은 순으로 정렬   
	visited[from] = true;
	
	while(!q.empty()) {
		int time = q.top().first;
		int loc = q.top().second;
		q.pop();
		
		// 동생위치에 도달하면 경과시간 반환  
		if(loc == to)
			return time;
			
		if(loc*2 < MAX && !visited[loc*2]) {
			q.push({time, loc*2}); // 순간이동의 경우 0초  
			visited[loc*2] = true;
		}	
		if(loc+1 < MAX && !visited[loc+1]) {
			q.push({time+1, loc+1});
			visited[loc+1] = true;
		}
		if(0 <= loc-1 && !visited[loc-1]) {
			q.push({time+1, loc-1});
			visited[loc-1] = true;	
		}
	}
}

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

	int N, K;
	cin>>N>>K;
	cout<<hiding(N, K);
	
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면