#1697: 숨박꼭질 (w/ BFS, Graph)

백준 1697번: 숨바꼭질

문제:

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

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

입력:

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

풀이:

이 문제는 브루트 포스 방식으로 무식하게 모든 경우의 수를 그래프 형태의 data structure를 이용하면서 bfs(breadth first search)로 가지 뻗기를 하면서 원하는 답 K에 도달하면 그때의 값을 리턴 하는 식으로 풀면 된다.

출처: 코딩 팩토리 https://coding-factory.tistory.com/610

여기서 일반 bfs와의 차이점은 내가 가지를 만들어 나가면서 문제를 푸는 것이다. 보통 search(탐색)이라고 하면 주어진 데이터에서 찾는 것을 생각하지만 이 경우에서는 현재 시작한 데이터(5)를 기반으로 가지를 만들면서 푸는 것이다. 어떻게 보면 이것 또한 답을 “찾는” 것이니까 search라고 할 수 있을 것 같긴 하다.

bfs를 배울 때는 알았지만 이 문제를 풀 때 생각 못한 것은 이미 확인한 값에 도달 했을 때 쓸 때 없이 또 가지 뻗기를 하지 않는 것이다. 이렇게 하면 time complexity와 memory 사용량도 줄일 수 있어서 시간 초과나 메모리 용량 초과로 틀릴 위험도 줄여 준다.

또한, seconds를 어떤 식으로 해야 한칸 씩 내려갈 때 마다 1씩 늘어나게 구현 할 수 있을지 고민 하다가 깨달은 것은 큐를 애초에 pair로 만들면 두가지 데이터를 동시에 저장 할 수 있다는 것이다.

🔎무한 반복하는 코드 작성 시 loop를 끝내는 if를 먼저 적고 시작 하면 편하다.

🔎bfs는 먼저 기본 값을 큐에 push하고 while loop에서 먼저 기본 값을 저장한 뒤 pop해준 뒤 그 다음 필요 연산을 한 뒤 다시 loop을 돌아서 저장하는 방식으로 구현 하면 된다.

코드:

#include <iostream>
#include <queue>

using namespace std;

bool visit[100001];
queue<pair<int, int> > q;
int N, K, answer;

bool check(int coord){
	if(coord < 0 || coord > 100000 || visit[coord]) return false;
	return true;
}

void bfs(int n){
	q.push({n,0});
	
	while(!q.empty()){
		int coord = q.front().first;
		int seconds = q.front().second;
		q.pop();
		if(coord == K){
			answer = seconds;
			break;
		}
		if(check(coord-1)){
			visit[coord-1] = true;
			q.push({coord-1, seconds+1});
		}
		if(check(coord+1)){
			visit[coord+1] = true;
			q.push({coord+1, seconds+1});
		}
		if(check(coord*2)){
			visit[coord*2] = true;
			q.push({coord*2, seconds+1});			
		}
		
	}
}

int main(void){
	cin >> N >> K;
	bfs(N);
	cout << answer;
	
}