백준 숨바꼭질

해당 문제는 백준온라인 저지에서 나온 문제입니다.

해결 방식

너비 우선 탐색 알고리즘(BFS)을 베이스로 작성하였습니다.

해결 방식을 고른 이유

완전탐색을 요구하는 문제로 깊이우선탐색으로는 정확한 해를 찾을 수 없다고 생각하여, 너비우선탐색 알고리즘을 선택하여 작성하였습니다.

저는 깊이우선방식과 너비우선방식 중에서 선택을 할때, 문제의 키워드를 보고 고릅니다.
대략적으로 최적의,가장 빠른 같은 키워드가 나올때는 너비우선탐색으로 진행하고, 그렇지 않은 경우 깊이우선탐색으로 코드를 짜는 편입니다.

코드

#include <iostream>
#include <queue>

using namespace std;

queue<int> ql;
queue<int> qc;
int visted[100001];
void push_q(int range, int cnt)
{
	ql.push(range);
	qc.push(cnt);
}

void	pop_q(int* range, int* cnt)
{
	*range = ql.front();
	ql.pop();
	*cnt = qc.front();
	qc.pop();
}

int main()
{
	int N, K;
	int	range, c;
	range = 0;
	c = 0;
	cin >> N >> K;
	push_q(N, 0);
	visted[N] = 1;
	while (qc.size() != 0 && ql.size() != 0)
	{
		pop_q(&range, &c);
		if (range == K)
		{
			cout << c << endl;
			break;
		}
		if (range + 1 <= 100000 && visted[range + 1] == 0)
		{
			push_q(range + 1, c + 1);
			visted[range + 1] = 1;
		}
		if (range * 2 <= 100000 && visted[range * 2] == 0)
		{
			push_q(range * 2, c + 1);
			visted[range * 2] = 1;
		}
		if (range - 1 <= 100000 && visted[range - 1] == 0 && range - 1 >= 0)
		{
			push_q(range - 1, c + 1);
			visted[range - 1] = 1;
		}
	}
}

코드 해설

주변에 존재하는 모든 노드를 넣고 탐색을 진행하는 너비 우선 탐색은 큐를 사용하여 작성하는것이 편합니다.
visted 변수는 같은 수를 계산하지 않기 위해서 넣은 것입니다. 예를 들어서
N =1, K = 1000의 경우, 맨 처음 while문에서 2,2,0의 값이 들어갑니다. 다음 반복에서 2를 꺼내어 3,4,1을 넣을 것이고, 그 다음 반복문에서도 2를 꺼내 3,4,1을 넣습니다. 이처럼 같은 값이 반복되서 들어가는 것을 막기 위해 visted변수를 놓아 중복을 막는것입니다.
계속 push,pop을 반복하며 pop한 값이 K값과 같다면 c를 출력하고 반복문을 끝냅니다.