https://www.acmicpc.net/problem/1697
문제
> 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
> 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.
> 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
> 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.접근
그래프 탐색중 너비우선탐색(BFS)를 이용해 수빈이가 갈 수 있는 x에 대해 탐색을 한다.
탐색을 하며 이동할 때마다 1초씩 누적하며 최종 K에 도달했을 때 누적된 초를 출력한다.
문제해결
> BFS함수를 정의해준다. 첫 수빈이의 위치를 받고 큐에 넣어준뒤 첫 좌표를 다시 탐색하지않도록 탐색 했다고 표시하기 위해 1초의 값을 누적시켜준다.
> 만약 현재 탐색 노드가 원하는 값인 K라면 K인 현재의 위치까지 오는데 누적된 시간 x == k 이므로 position[x]를 리턴해주는데 앞서 중복방지로 1초를 추가했기에 1초 빼주고 리턴한다.
> 진행가능한 위치에 대해 정의해준다. x-1, x+1, x*2가 가능하다고 했다. 앞서 q.front()로 받아온 x값 즉 부모노드의 위치로 해당 dir을 계산해주고 이를 반복문의 범위로 넣고 자식노드를 구해 큐에 넣어준다.
> 계산한 위치 a가 범위를 넘어가면 안되므로 주어진 범위 0<= N <= 100,000 일때 탐색노드로 넣고 또, 해당 위치를 탐색 하지않았음(position[a] == 0)일 때 넣어준다.
> 다음 탐색노드, 즉, 위치를 넣어줄 때 해당 위치의 벡터값으로 누적된 부모노드 + 1초 해서 넣어준다. 그래야 최종 결과 출력시 해당 위치 까지 오는데 누적된 시간을 구할 수 있다.
> main함수에서 받을 입력을 다 받아주고 BFS함수를 호출해 결과를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, K;
int Max = 100000;
vector<int> position;
int BFS(int start)
{
queue<int> q;
q.push(start);
position[start] = 1;
while (!q.empty())
{
int x = q.front();
q.pop();
if (x == K) return position[x] - 1;
int dir[3] = { x - 1, x + 1, x * 2 };
for (auto a : dir)
{
if (a >= 0 && a <= Max && position[a] == 0)
{
position[a] = position[x] + 1;
q.push(a);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
position.assign(Max+1, 0);
cin >> N >> K;
cout << BFS(N) << '\n';
}
후기
기존에 쓰던 BFS는 탐색용도로 모든 점을 방문하여 방문 처리하는 부울벡터가 있었는데 방문까지 소요된 시간을 누적하여 이를 통해 처리하는거에서 새로운 알고리즘 처럼 느껴졌다.
