알고리즘/백준 문제풀이
백준 1697번 - 숨바꼭질
엠씨비기
2020. 9. 7. 23:16
1697번: 숨바꼭질
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 ��
www.acmicpc.net
더보기
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
queue<int> Que;
int visit[100001] = { 0, };
int dist[100001] = { 0, };
int main(int argc, char* argv[])
{
int n, k; //형의 위치, 동생의 위치
scanf("%d %d", &n, &k);
Que.push(n);
visit[n] = 1;
dist[n] = 0;
//형과 동생이 동일한 위치에 있으면 0을 출력
if (n == k)
{
printf("%d\n", dist[k]);
return 0;
}
while (!Que.empty())
{
int temp = Que.front();
Que.pop();
// 형의 위치(n)에서 n+1로 이동
if (temp + 1 <= 100000 && visit[temp+1] == 0)
{
Que.push(temp + 1);
visit[temp + 1] = 1;
dist[temp + 1] = dist[temp] + 1;
if (temp + 1 == k)
{
printf("%d\n", dist[temp + 1]);
break;
}
}
// 형의 위치(n)에서 n-1로 이동
if (temp - 1 >= 0 && visit[temp - 1] == 0)
{
Que.push(temp - 1);
visit[temp - 1] = 1;
dist[temp - 1] = dist[temp] + 1;
if (temp - 1 == k)
{
printf("%d\n", dist[temp - 1]);
break;
}
}
// 형의 위치(n)에서 n*2로 이동
if (temp * 2 <= 100000 && visit[temp * 2] == 0)
{
Que.push(temp * 2);
visit[temp * 2] = 1;
dist[temp * 2] = dist[temp] + 1;
if (temp * 2 == k)
{
printf("%d\n", dist[temp*2]);
break;
}
}
}
return 0;
}