1697.숨바꼭질

1697번: 숨바꼭질

이번에 풀어볼 문제는 백준의 1697 숨바꼭질이다. 어떻게 접근을 시작하는지, 설계를 시작하는지에 따라

체감하는 난이도는 크게 차이가 날 것 같다. 나같은 경우에는 금방 풀이법을 찾아냈다.

대부분이 금방 찾아내는 경우라면 쉬운편에 속하는 것이고 아닌 사람들 굉장히 헤맬 것이다.

결론을 말하자면 이번문제는 BFS로 간단하게 풀어낼 수 있는 문제이다.

주의할 점이 있다면 같은 연산을 줄이는 것이다.

이것만 주의하면 충분히 풀 수 있는 문제이다!! 

# 배열을 선언했다면 연산 범위를 주의해야한다 => 그렇지않으면 런타임 에러 지옥에 빠질 수도 있다.

# 또다른 실수로는 불필요한 연산이 늘어나면 시간초과를 겪을 수 있다.

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#define MAX 100001
using namespace std;

int n, k; //n이 수빈, k가 동생

int check[MAX]; // 연산한 적이 있는 값을 체크하는 유무이다. 0으로 초기화

int brute(){
	queue<int>q; // 탐색할 숫자가 저장되는 큐
	q.push(n); // 시작 값이 저장
	check[n] = 1; // 시작값을 1로 초기화 => 0으로 초기화하면
                  // 아래의 로직으로인해 여러번 계산하게 되므로 주의!!
                 
	while (!q.empty()){
		int x = q.front(); // 큐의 값 사용
		q.pop(); // 위에서 저장했으므로 큐에서 제거
		if (check[k]) // 우리가 찾는 값이 true가 되면
			return check[k]; // 그 값을 리턴하고 종료
		if (x - 1 >= 0 && !check[x - 1]){ // "큐의 값 - 1"의 조건
			check[x - 1] = check[x] + 1; // 성립시 이전의 값 + 1을 저장
			q.push(x - 1); // 해당 숫자 큐에 저장
		}
		if (x + 1 < MAX && !check[x + 1]){ // "큐의 값 + 1"의 조건
			check[x + 1] = check[x] + 1;// 성립시 이전의 값 + 1을 저장
			q.push(x + 1); // 해당 숫자 큐에 저장
		}
		if (x * 2 < MAX  && !check[x * 2]){// "큐의 값 * 2"의 조건
			check[x * 2] = check[x] + 1;// 성립시 이전의 값 + 1을 저장
			q.push(x * 2); // 해당 숫자 큐에 저장
		}
	}
}

int main() {
	freopen("1697.txt", "r", stdin);
	cin >> n >> k;
	cout << brute()-1 << "\n"; // 리턴값 출력
	return 0;
}

 

 

< 로직 설명 >

위의 코드를 그림으로 표현하자면  다음과 같다. 그림을 보면 이해가 빠를 것이다. 

이미 진행된 연산을 check 배열로 판단해서 있으면 굳이 값을 저장하여 탐색하지 않는 로직이다.