BaekJoon 1697 숨바꼭질

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

소스결과 : 3284 KB / 8 ms

출처 : Backjoon , USACO US Open 2007 Contest Sliver 2번

언어 : C++14

 

설명

분류는 백트래킹인데 질문 게시판을 보니 왜 백트래킹 문제인지 궁금하다는 문제

일단 BFS로 풀었는데 DFS로 풀면 시간 내에 돌아갈지 궁금하다

Local에서 몇가지 케이스를 돌렸을 때 제한 시간보다 오래 걸렸는데 맞았다고 뜨는거보니 신기하기도 하다

 

구현은 범위를 구분해서 +-1을 한 결과를 보거나 *2 를 하면 되는 경우인데

최대가 100,000이라해서 수빈이가 100,000을 넘어가면 안된다 라는 조건을 걸면 틀리는 문제

반례를 찾기 어려운 문제라 반례를 찾는데 시간을 좀 투자했다.

 

알고리즘

1. 방문을 확인하기위한 배열 생성

2. 수빈이의 위치와 동생의 위치를 입력

3. 수빈이의 위치와 동생의 위치가 똑같은지 확인

 3.1 똑같으면 5번으로

4. 수빈이 위치를 queue에 추가후 BFS진행

 3-1 수빈이의 위치가 0보다 크면 다음 방문 Queue에 현재 위치 -1 push

 3-2 수빈이의 위치가 동생의 위치보다 작으면 다음 방문 Queue에 현재위치 + 1 push

 3-3 수빈이의 위치 * 2 가 최대 범위(110,000) 보다 작으면 다음 방문 Queue에 현재위치 * 2 push

5. 동생 위치를 탐색했는지 확인

 4-1 발견 하지 못했으면 다음 방문 Queue에 있는 원소를 방문 해야할 Queue에 push 후 step +1 

 4-2 BFS 중단

5. 출력

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

bool check[110001];

int main()
{
	int subin, bro;
	int step = 0;
	bool found = false;
	queue<int> curQ;
	queue<int> nextQ;

	cin >> subin >> bro;

	if (subin != bro)
	{
		curQ.push(subin);

		while (!found)
		{
			while (!curQ.empty())
			{
				int cur = curQ.front();
				curQ.pop();

				if (cur == bro)
				{
					found = true;
					break;
				}
					
				check[cur] = true;

				if (cur > 0 && !check[cur - 1])
					nextQ.push(cur - 1);
				if (cur < bro && !check[cur + 1])
					nextQ.push(cur + 1);
				if (cur * 2 < 110000 && !check[cur * 2])
					nextQ.push(cur * 2);
			}

			if (!found)
			{
				while (!nextQ.empty())
				{
					curQ.push(nextQ.front());
					nextQ.pop();
				}
				step++;
			}

		}
		
	}

	cout << step;

	return 0;
}