알고리즘 문제풀이
[백준/BOJ] 백준 13549번 : 숨바꼭질 3
GeniusJo
2020. 9. 24. 12:51
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 ��
www.acmicpc.net
there로 이동할 때 지금 이동하는 depth가 기존 there의 depth보다 더 작을 경우에만 이동하면서 탐색을 진행했다.
코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int depth[100001];
void Pre()
{
for (int i = 0; i < 100001; i++)
depth[i] = 987654321; //매우 큰 수로 초기화
}
void Solve(int start, int dest)
{
Pre();
depth[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty())
{
int here = q.front();
q.pop();
//목적지에 도착했을때
if (here == dest)
continue; //현재 depth이상의 depth로는 탐색하지는 않는다
for (int i = 0; i < 3; i++)
{
int there = here;
if (i == 0) //앞쪽으로 걷기
there++;
else if (i == 1) //뒤쪽으로 걷기
there--;
else if (i == 2) //순간이동
there = there * 2;
//there로 이동할때 지금 이동하는 depth가 기존 there의 depth보다 더 작을 경우에만 이동한다
if (there >= 0 && there <= 100000)
{
if (i == 0 || i == 1)
{
if (depth[there] > depth[here] + 1)
{
depth[there] = depth[here] + 1;
q.push(there);
}
}
else if (i == 2) //순간이동일때
{
if (depth[there] > depth[here])
{
depth[there] = depth[here];
q.push(there);
}
}
}
}
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, k;
cin >> n >> k;
Solve(n, k);
cout << depth[k];
return 0;
}