[BAEKJOON] 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는 정수이다.

 

입력

5 17

 

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

4

 

 

풀이

수빈이의 현재 위치부터 이동가능한 3가지 경로에 대하여 너비 우선 탐색(BFS)을 수행하면 됨

이동한 위치를 저장할 용도로 생성한 queue에 위치, 시간 정보를 push해 인접 노드부터 순차적으로 탐색함

(이때 queue는 위치, 시간 정보를 저장하기 위해 pair로 만듬)

동생의 위치에 도달할 경우 도착한 시간 반환 및 출력

int bfs() 
{
	// 출발 위치, 시간 push 후 방문 처리
	q.push(make_pair(n, 0));
	visit[n] = 1;

	while (!q.empty()) 
	{
		// 현재 노드 기억
		int nowposition = q.front().first;
		int nowsecond = q.front().second;
		q.pop();

		// 목표 위치 도달시 break
		if (k == nowposition) return nowsecond;

		// 걷는경우(x - 1, x + 1), 순간이동 하는 경우( 2 * x) //범위, 방문 확인 후 큐에 push
		if (nowposition - 1 >= 0 && visit[nowposition - 1] == 0) {
			q.push({ nowposition - 1, nowsecond + 1 });
			visit[nowposition - 1] = 1;
		}
		if (nowposition + 1 < 100001 && visit[nowposition + 1] == 0) {
			q.push({ nowposition + 1, nowsecond + 1 });
			visit[nowposition + 1] = 1;
		}
		if (nowposition * 2 < 100001 && visit[nowposition * 2] == 0) {
			q.push({ nowposition * 2, nowsecond + 1 });
			visit[nowposition * 2] = 1;
		}
	}
}

 

전체 코드

#include <iostream>
#include <queue>

using namespace std;

// 방문 확인용 배열
int visit[100001] = { 0 };

// 너비 우선 탐색용 큐 (위치, 시간 저장)
queue<pair<int, int>> q;

// 수빈이의 위치, 동생의 위치
int n, k;

int bfs() 
{
	// 출발 위치, 시간 push 후 방문 처리
	q.push(make_pair(n, 0));
	visit[n] = 1;

	while (!q.empty()) 
	{
		// 현재 노드 기억
		int nowposition = q.front().first;
		int nowsecond = q.front().second;
		q.pop();

		// 목표 위치 도달시 break
		if (k == nowposition) return nowsecond;

		// 걷는경우(x - 1, x + 1), 순간이동 하는 경우( 2 * x) //범위, 방문 확인 후 큐에 push
		if (nowposition - 1 >= 0 && visit[nowposition - 1] == 0) {
			q.push({ nowposition - 1, nowsecond + 1 });
			visit[nowposition - 1] = 1;
		}
		if (nowposition + 1 < 100001 && visit[nowposition + 1] == 0) {
			q.push({ nowposition + 1, nowsecond + 1 });
			visit[nowposition + 1] = 1;
		}
		if (nowposition * 2 < 100001 && visit[nowposition * 2] == 0) {
			q.push({ nowposition * 2, nowsecond + 1 });
			visit[nowposition * 2] = 1;
		}
	}
}

int main(void) 
{
	cin >> n >> k;

	cout << bfs() << endl;

	return 0;
}