[BFS]-연습-숨바꼭질

< BFS > - < 실버 1 >

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

1697번: 숨바꼭질

---

[ 1697 ] 숨바꼭질

 

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

 

:: 입력 ::

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

:: 출력 ::

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

 

처음에는 BFS가 아니라 단순한 반복문과 조건문을 섞어서 풀려고 했는데 그렇게 해도 풀리긴하지만 연산이 너무 많아지고 문제 출제 의도랑도 안 맞는 거 같아서 BFS를 활용한 풀이를 고민함 근데 원래 BFS를 돌릴 땐 +1 -1 같은 것만 있어서 배열에 값을 넣어 해결할 수 있었는데 이번엔 *2도 있어서 어케 해야될 지 모르겟는거임 그래서 정답 코드를 보고 range-based for문을 저렇게도 쓸 수 있다는 걸 배움 !

 

  정답  코드  

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int board[100002]; // 동생을 찾는 과정에서 아무리 멀리 가도 200000을 넘지 않음

int main() {

	int n, k;
	cin >> n >> k;

	queue<int> q;
	q.push(n);

	fill(board, board + 100001, -1);
	board[n] = 0;

	while (board[k] == -1) { // k에 도달할때까지 q가 빌때까지로 돌리면 불필요하게 모든 칸을 다 탐색하게 됨
		int num = q.front();
		q.pop();

		// 아래의 세 숫자를 어떻게 for문으로 돌릴지가 안 떠올라서 정답 코드 봄
		/*int a = num + 1;
		int b = num - 1;
		int c = num * 2;*/

		// 이런 방식의 range-based for문도 가능
		for (int nxt : {num - 1, num + 1, num * 2}) {
			if (nxt < 0 || nxt > 100001)continue;
			if (board[nxt] != -1) continue;

			board[nxt] = board[num] + 1;
			q.push(nxt);
		}
	}

	cout << board[k];
}