1697번: 숨바꼭질 (BOJ C/C++)

1697번: 숨바꼭질

사용 언어: C++

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

첫 번째 풀이

queue+pair을 이용해 경우를 if문으로 나눠서 푼 보편적인 풀이다.

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001
#define X first;
#define Y second;
int N, K;
int dist[MAX];

int BFS(int N, int K)
{
	queue<pair <int, int>> Q;
	Q.push({N,0});
	dist[N] = 1;
	
	while(!Q.empty())
	{
		int cur = Q.front().X;
		int time = Q.front().Y;
		Q.pop();
		
		if(cur == K)
			return time;
		
		if(cur+1 < MAX && !dist[cur+1])
		{
			Q.push({cur+1, time+1});
			dist[cur+1]=1;
		}
		if(cur-1 >= 0 && !dist[cur-1])
		{
			Q.push({cur-1, time+1});
			dist[cur-1]=1;
		}
		if(cur*2 < MAX && !dist[cur*2])
		{
			Q.push({cur*2, time+1});
			dist[cur*2]=1;
		}
	}
	return 0;
}
	
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N>>K;
	cout<<BFS(N,K)<<'\n';
	
	return 0;
}

 

두 번째 풀이

바킹독님의 풀이인데, 사실 위 풀이보다 더 간단명료하긴 한데 평소에 안 쓰는 개념이 있다보니 두 번째 풀이로 분류했다. 일단 가장 큰 차이점은 위 풀이는 답이 될 index를 따로 저장했지만 여기서는 배열의 값에 index를 저장한다는 것이다. 평소에 안 쓰는 개념은

for(int nxt : {cur-1, cur+1, cur*2})

이렇게 for문을 쓰는 것을 처음 봐서 따로 빼놨다. 아마도 int nxt에 각각 cur-1, cur+1, cur*2 을 대입해서 for 문을 돌리는 형식 같다.

#include <bits/stdc++.h>
using namespace std;

int dist[100002];
int N, K, temp;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	fill(dist, dist+100001, -1);
	dist[N] = 0;
	queue<int> Q;
	Q.push(N);
	while(dist[K] == -1)
	{
		int cur = Q.front();
		Q.pop();
		for(int nxt : {cur-1, cur+1, cur*2})
		{
			if(nxt<0 || nxt>100000) continue;
			if(dist[nxt] != -1) continue;
			dist[nxt] = dist[cur]+1;
			Q.push(nxt);
		}
	}
	cout<< dist[K] << '\n';
	
	return 0;
}