C++) 백준 12851번 숨바꼭질2

 

문제

 

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

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

 

코드

 

#include <iostream>
#include <queue>

using namespace std;

bool vis[100002];

int main()
{
	queue<pair<int,int>> Q;
	int N, K;
	int Time = 0, Cnt = 0;

	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;

	Q.push({N,0});

	while (!Q.empty()) {
		int cur = Q.front().first; 
		int curTime = Q.front().second;
		Q.pop();
		vis[cur] = 1;
		
		if (cur == K && curTime == Time && Cnt)
			Cnt++;

		if (cur == K && !Cnt) {
			Cnt++;
			Time = curTime;
		}
		
		for (int nxt : {cur - 1, cur + 1, cur * 2}) {
			if (nxt < 0 || nxt > 100000) continue;
			if (vis[nxt]) continue;
			Q.push({ nxt,curTime + 1 });
		}
	}
	cout << Time << endl << Cnt;
}

 

 

풀이

 

<접근1>

숨바꼭질1의 방식을 사용하였다.

BFS에서 사용하는 visit 배열 대신 distance 배열을 사용하여

거리가 먼 순서대로 큐에 삽입됨을 이용해, 거리 순서대로 처리할 수 있게끔 한다.

 

distance 배열에서 동생의 위치에 해당하는 값이 갱신될 때까지 반복하다가
거리가 갱신되면 반복을 해제하고 큐를 다 비워 카운팅하려 하였다.
하지만 이 방식으론 같은 거리에서의 중복 (ex. 입력 1 4)을 처리할 수 없었다.

 

<접근2>

distance 배열 사용에서 visit 배열 사용으로 바꾼 후
조건을 사용해 중복을 처리하고 노력하였다.
하지만 계속된 메모리 초과로 해당 코드를 포기하였다.
원인은 아직도 알 수 없었지만, 반례들을 수없이 대입했을 때 오답은 없었다.

 

<접근3>

기존의 BFS 풀이 방식에서는 항상 push 후에 visit 처리를 하였다.

때문에 중복 처리를 하기 어려웠다.

숨바꼭질2는 같은 거리 내에서의 중복을 허용해야하는 문제였다.
(ex. 입력 1 4)
때문에 push후 visit이 아닌 pop후 visit으로 문제를 해결할 수 있었다.