[BOJ] 1697 숨바꼭질

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

Note

분류는 백트래킹인데 질문 게시판을 보니 왜 백트래킹 문제인지 궁금하다는 문제
일단 BFS로 풀었는데 DFS로 풀면 시간 내에 돌아갈지 궁금하다
Local에서 몇가지 케이스를 돌렸을 때 제한 시간보다 오래 걸렸는데 맞았다고 뜨는거보니 신기하기도 하다

구현은 범위를 구분해서 +-1을 한 결과를 보거나 *2 를 하면 되는 경우인데
최대가 100,000이라해서 수빈이가 100,000을 넘어가면 안된다 라는 조건을 걸면 틀리는 문제
반례를 찾기 어려운 문제라 반례를 찾는데 시간을 좀 투자했다.

알고리즘

1. 방문을 확인하기위한 배열 생성
2. 수빈이의 위치와 동생의 위치를 입력
3. 수빈이의 위치와 동생의 위치가 똑같은지 확인
   1. 똑같으면 5번으로
4. 수빈이 위치를 queue에 추가후 BFS진행
   1. 수빈이의 위치가 0보다 크면 다음 방문 Queue에 현재 위치 -1 push
   2. 수빈이의 위치가 동생의 위치보다 작으면 다음 방문 Queue에 현재위치 + 1 push
   3. 수빈이의 위치 2 가 최대 범위(110,000) 보다 작으면 다음 방문 Queue에 현재위치 2 push
5. 동생 위치를 탐색했는지 확인
   1. 발견 하지 못했으면 다음 방문 Queue에 있는 원소를 방문 해야할 Queue에 push 후 step +1 
   2. BFS 중단
6. 출력

소스코드

#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;
}

2019-01-08 14:00:00에 Tistory에서 작성되었습니다.