백준 1697번 - 숨바꼭질

수빈이와 동생이 숨바꼭질을 한다.

수빈이는 1초에 X-1 , X+1의 위치로 이동할 수 있고, 심지어 1초만에 2*X의 위치로도 이동이 가능하다 ㄷㄷ

입력으로 수빈이의 위치와 동생의 위치가 주어지는데, 수빈이가 몇 초 만에 동생을 잡을 수 있을지 출력하는 문제다.

 

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

//숨바꼭질 할 배열
int Spot[100001];

//수빈이 위치
int n;
//동생 위치
int k;

int dx[3] = { -1,1,2 };

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

	//수빈이와 동생의 위치가 같으면 0 출력 후 리턴
	if (n == k)
	{
		cout << 0; 
		return 0;
	}

	//시작 위치에 걸리는시간 1을 넣어줌 (나머지 배열을 다 -1로 다 바꿔주기 귀찮아서 1로 시작)
	Spot[n] = 1;

	queue<int> Q;
	Q.push(n);

	int x = 0;
	while (!Q.empty())
	{
		int cur = Q.front(); Q.pop();
		for (int i = 0; i < 3; i++)
		{
			if (i != 2) x = cur + dx[i];
			else x = cur * dx[i];

			//인덱스를 벗어나면 컨티뉴
			if (x < 0 || x > 100000) continue;

			//탐색하는 위치와 동생의 위치가 같으면 현재 spot까지 걸리는 시간 출력(시작을 1로 했기때문에 cur로 출력함)
			if (x == k)
			{	
				cout << Spot[cur];
				return 0;
			}
			//이미 탐색을 해서 거리의 값이 들어간 스팟이면 컨티뉴
			if (Spot[x] > 0) continue;

			Spot[x] = Spot[cur] + 1;
			Q.push(x);
		}
	}

	return 0;
}

사실 지금은 문제만 읽고 어떤 알고리즘을 써서 풀어야하는지 잘 떠오르지가 않는다.

아마 이 문제도 bfs로 풀수있다 라는 확신이 없었다면 시간이 더 많이 소요됐을것 같다.

 

bfs의 정형화된 틀을 이용해서 동생을 탐색하는 코드를 짰는데 맞다고 생각하는 코드였는데도 계속 실패해서 뭐가 틀렸는지 한참 찾았다.

 

내가 처음에 짠 코드는 수빈이와 동생이 같은 위치에 있을때 0이라는 값을 출력하지 못했다.

그래서 전체 코드를 수정하지않고 급하게 n==k 라면 0을 출력하고 종료를 시키는 코드를 추가하니 맞았다.

 

코테여서 출력값만 잘 나오면 된다지만, 현재 코드가 깔끔하지 못하고 다음번에 짤때는 더 효율적으로 짜기위해 다른 고수분이 짠 코드를 참고해서 다시 짜봤다.

 

#include<iostream>
#include<queue>
#include<utility>

using namespace std;

//숨바꼭질 할 배열
int Spot[100001];

//수빈이 위치
int n;
//동생 위치
int k;

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

	//시작 위치에 걸리는시간 1을 넣어줌 (나머지 배열을 다 -1로 다 바꿔주기 귀찮아서 1로 시작)
	Spot[n] = 1;

	queue<int> Q;
	Q.push(n);

	while (Spot[k] == 0)
	{
		int cur = Q.front(); Q.pop();
		for (int x : {cur+1,cur-1,cur*2})
		{	
			//인덱스를 벗어나면 컨티뉴
			if (x < 0 || x > 100000) continue;

			//이미 탐색을 해서 거리의 값이 들어간 스팟이면 컨티뉴
			if (Spot[x] > 0) continue;

			Spot[x] = Spot[cur] + 1;
			Q.push(x);
		}
	}

	//1로 시작했기 때문에 들어간 값에 -1을 해줌
	cout << Spot[k]-1;

	return 0;
}

 

원래는 dx라는 int형 배열에 {-1,+1,2} 를 넣어서 if문을 통해 x에 값을 넣어주었는데,

for (int x : {cur+1,cur-1,cur*2}) 이 코드로 for문을 돌리니 코드가 한결 깔끔해졌다.

 

또 while문의 조건을 바꿔주었는데, Spot[k]가 0일때만 while문이 돌아가는 조건을 설정했다.

즉, 동생의 위치에 어떠한 거리의 값이 들어가면 while문을 탈출해 거리값을 출력하고, 만약에 수빈이와 동생의 거리가 같다면 처음에 Spot[n] = 1을 통해 1이라는 값을 넣어주었기 때문에 Spot[k]도 1이므로 while문이 시작되지 않는다.

 

깔끔한 코드를 위해 더 연습해야겠다..