[bfs] 1697 숨바꼭질

숨바꼭질 (1697)

 

풀이코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
// 1697 숨바꼭질

const int MAX = 100000;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 

	int start, end;
	int distance[MAX + 1];
	fill_n(distance, MAX + 1, -1);
	queue<int> q;
	
	cin >> start >> end;
	
	distance[start] = 0;
	q.push(start);
	
	bool ok = true;

	while(ok){
		int currentNode = q.front();
		q.pop();
		
		int nextNodes[3] = {currentNode - 1, currentNode + 1, currentNode * 2};
		
		for(int nextNode : nextNodes){
			if(nextNode > MAX || nextNode < 0) continue;
			if(distance[nextNode] == -1){
				q.push(nextNode);
				distance[nextNode] = distance[currentNode] + 1;
			}
			if(nextNode == end) ok = false;
		}
	}
	cout << distance[end] << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

간선의 개수가 10억개 이렇게 엄청나게 커지면 안될 것이다. O(간선의 개수) 이기 때문.

비슷한 문제 (미로탐색)

풀이

1. 위의 그림의 모든 조건을 만족하기 때문에, BFS 로 풀어볼 수 있다.

2. 범위에 주의해야 한다.

- 범위는 *2 연산이 있기에 20만을 절대 넘을 수 없다. 하지만, 10만을 넘겨 *2를 하는 것은 절대 최소가 될 수 없으므로 필자는 그냥 10만에 제한을 걸었다.

3. distance 배열로 시작점 부터 지금까지의 거리 와 방문 여부 둘 다 체크해주 었다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점