Koala - 11기/코딩테스트 준비 스터디
[C++] 백준 12851번: 숨바꼭질 2
luciduskim
2023. 8. 27. 21:00
https://www.acmicpc.net/problem/12851
12851번: 숨바꼭질 2
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
1. 문제풀이
위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 후, 목표 위치에 도달하면 해당 시간을 저장하고 결괏값을 1증가시킨다. 큐에 남아있는 정보에서 이동 시 목표 위치에 도달할 경우 결괏값을 1증가시키고, 목표 위치에 도달한 시간이 저장된 시간을 초과하면 너비 우선 탐색을 종료한다.
2. C++ 코드
#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
using namespace std;
int res, cnt;
int visited[100001];
void search(int from, int to)
{
queue<pair<int, int>> q;
q.push(make_pair(0, from));
while (!q.empty()) {
int time = q.front().first;
int pos = q.front().second;
visited[pos] = 1;
q.pop();
if (pos == to) {
res = time;
cnt++;
}
if (visited[to] && res < time) {
return;
}
if (pos - 1 >= 0 && !visited[pos - 1]) {
q.push(make_pair(time + 1, pos - 1));
}
if (pos + 1 <= 100000 && !visited[pos + 1]) {
q.push(make_pair(time + 1, pos + 1));
}
if (pos * 2 <= 100000 && !visited[pos * 2]) {
q.push(make_pair(time + 1, pos * 2));
}
}
}
int main(void)
{
int n, k;
scanf("%d %d", &n, &k);
search(n, k);
printf("%d\n%d\n", res, cnt);
return 0;
}