백준 1697(숨바꼭질)

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

1697번: 숨바꼭질

 

 

조건들을 추가해서 더 쉽게 접근할 수 있을까. 고민을 해보았지만, 반례들이 존재했다. 그래서 그냥 bfs로 완전탐색을 하였다. dfs대신 bfs를 선택한 이유는 이 문제는 전형적인 턴제의 문제여서이다. 그리고 만약에 dfs로 접근을 한다면, 멈출 조건을 설정하는 것이 너무 까다롭게 된다. 

 

그래서 턴제의 bfs를 선택하였다. 

 

*2 , +1, -1 을 계속해서 한 뒤에 몇 번을 해야지 최소가 나올까 인데, 만약에 bfs로 한다면 모든 경우에 대해서 구한 뒤 그 중 최솟값을 결정하는게 아니라 무조건 최소의 경우가 결괏값으로 한번에 저장이 된다. 

 

그리고, 배열 index 범위초과 접근에 대해서 주의하자. 범위를 벗어나게 된다면 런타임 에러가 발생한다.  

 

만약 if(v[index-1] > 0 && index > 0) 이런 조건문이 있다고 한다면, v[index-1] > 0 에 대해서 조사를 한 뒤에 그 다음 조건에 대해서 확인을 하기 때문에, index>0조건을 먼저 넣는 것이 중요하다. 

 

 

그리고 대부분의 그래프 문제와 같이 visited를 잘 사용하는 것이 중요하다.

#include<iostream>
#include<queue>
using namespace std;
#define MAX 100002

int N, K, cnt=1, tmp;
bool visited[MAX] = { false };
bool answer = false;
queue<int> q;
queue<int> q2;

void bfs() {
	while (1) {
		while (!q.empty()) {
			tmp = q.front();
			q.pop();
			if (tmp<MAX && !visited[tmp + 1]) {
				q2.push(tmp + 1);
				visited[tmp + 1] = true;
				if ((tmp + 1) == K) answer = true;
			}
			if (tmp>0 && !visited[tmp - 1]) {
				q2.push(tmp - 1);
				visited[tmp - 1] = true;
				if ((tmp - 1) == K) answer = true;
			}
			if (2*tmp <= MAX && !visited[2 * tmp]) {
				q2.push(2 * tmp);
				visited[2 * tmp] = true;
				if ((2 * tmp) == K) answer = true;
			}
			if (answer) {
				cout << cnt << "\n";
				return;
			}
			if (q.empty()) cnt++;
		}
		while (!q2.empty()) {
			tmp = q2.front();
			q2.pop();
			if (tmp < MAX && !visited[tmp + 1]) {
				q.push(tmp + 1);
				visited[tmp + 1] = true;
				if ((tmp + 1) == K) answer = true;
			}
			if (tmp > 0 && !visited[tmp - 1]) {
				q.push(tmp - 1);
				visited[tmp - 1] = true;
				if ((tmp - 1) == K) answer = true;
			}
			if (2*tmp <= MAX && !visited[2 * tmp]) {
				q.push(2 * tmp);
				visited[2 * tmp] = true;
				if ((2 * tmp) == K) answer = true;
			}
			if (answer) {
				cout << cnt << "\n";
				return;
			}
			if (q2.empty()) cnt++;
		}
	}
}

int main() {
	cin >> N >> K;
	if (N == K) {
		cout << 0 << "\n";
		return 0;
	}
	q.push(N);
	visited[N] = true;
	bfs();
}