[Baekjoon] 1697번: 숨바꼭질

🥅 문제

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

 

🔍 설계

현재 위치를 x라고 할 때, 그 위치에서 +1, -1, *2의 위치로 이동할 수 있으므로, 큐에서 현재 위치를 꺼내 매 초마다 이동할 수 있는 새로운 위치를 갱신한다. 

 

큐가 빌 때까지 하는데, 어떤 초에 놓여져 있는 위치로부터 다음 초에 이동할 위치 얻어내는 과정에서 이동하기 전 size를 저장하고, 반복문을 사용하였다.

 

다음 초에 이동할 수 있는 위치의 범위를 반드시 확인해야 한다.

 

어떤 위치에 이미 이동했고, 그로 인해 새로운 위치를 얻어냈는데, 나중에 또 방문한다면 중복이 일어나 메모리 초과, 시간 초과가 발생하므로 어떤 위치에 이동한 시각을 visited에 저장하여 저장된 시각보다 도착한 시각이 크다면 큐에 추가하지 않는다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;	
int n, k, sec=0;
vector<int> visited(100001, 1e9+7);

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	if (n==k){
		cout << 0 << "\n";
		return 0;
	}		
	queue<int> q;
	q.push(n);
	while (!q.empty()){
		sec+=1;
		int size = q.size();
		for (int i=0; i<size; i++){
			int x = q.front();
			q.pop();
			if (x+1 <= 100000){
				if (visited[x+1] > sec){
					visited[x+1] = sec;
					q.push(x+1);
				}
			} 
			if (x-1 >= 0){
				if (visited[x-1] > sec){
					visited[x-1] = sec;
					q.push(x-1);
				}
			} 
			if (x*2 <= 100000){
				if (visited[x*2] > sec){
					visited[x*2] = sec;
					q.push(x*2);
				}
			} 
		}
	}
	cout << visited[k] << "\n";
	return 0;
}