BOJ 1697. 숨바꼭질

🙇‍♀️[Silver I] 숨바꼭질 - 1697

문제 링크

성능 요약

메모리: 2676 KB, 시간: 0 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 1월 3일 19:38:38

문제 설명

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

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

입력

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

출력

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

🚀풀이

처음에 DFS로 하려고 했는데 DFS로 하면 안된다는걸 알았다.

+1, -1, *2 하는 값들이 레벨별로 내려오니까 트리 구조로 생각해서 풀었다.

그리고 만약 5에서 시작해서 -1한 값으로 4가 되고 다시 +1을 해서 5가되면 의미 없는 반복이니 다시 되돌아가지 않게 만들어줘야한다.

한마디로 BFS로 해결해야하는 문제이다.

int n, k;
int discovered[100001];
void BFS(int here)
{
	queue<pair<int, int>> q;
	q.push({ here, 0 });
	discovered[n] = true;
	while (q.empty() == false)
	{
		int here = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (here == k)
		{
			cout << cnt;
			return;
		}
		if (here + 1 < 100001)
		{
			if (discovered[here + 1] == false)
			{
				discovered[here + 1] = true;
				q.push({ here + 1, cnt + 1 });
			}
		}
		if (here - 1 >= 0)
		{
			if (discovered[here - 1] == false)
			{
				discovered[here - 1] = true;
				q.push({ here - 1, cnt + 1 });
			}
		}
		if (here * 2 >= 0 && here * 2 < 100001)
		{
			if (discovered[here * 2] == false)
			{
				discovered[here * 2] = true;
				q.push({ here * 2, cnt + 1 });
			}
		}
	}
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, k;
int discovered[100001];
void BFS(int here)
{
	queue<pair<int, int>> q;
	q.push({ here, 0 });
	discovered[n] = true;
	while (q.empty() == false)
	{
		int here = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if (here == k)
		{
			cout << cnt;
			return;
		}
		if (here + 1 < 100001)
		{
			if (discovered[here + 1] == false)
			{
				discovered[here + 1] = true;
				q.push({ here + 1, cnt + 1 });
			}
		}
		if (here - 1 >= 0)
		{
			if (discovered[here - 1] == false)
			{
				discovered[here - 1] = true;
				q.push({ here - 1, cnt + 1 });
			}
		}
		if (here * 2 >= 0 && here * 2 < 100001)
		{
			if (discovered[here * 2] == false)
			{
				discovered[here * 2] = true;
				q.push({ here * 2, cnt + 1 });
			}
		}
	}
}

void solve()
{
	cin >> n >> k;

	BFS(n);
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}