https://www.acmicpc.net/problem/13549
13549번: 숨바꼭질 3
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때
www.acmicpc.net
이 문제의 경우 반례를 생각 못해서 틀렸다 기존 코드에서 일반적인 반례는 잘 나왔으나 0 1을 입력했을 때 0 이 나와야 했는데 기존의 코드가 게속 1을 출력했다. 이 부분을 해결하니 해결되었다
#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
int visited[100001];
int N, K;
int main() {
cin >> N >> K;
queue<int> hs;
hs.push(N);
memset(visited, -1, sizeof(visited));
visited[N] = 0;
while (true) {
if (hs.front() == K) {
break;
}
if (hs.front() <= 50000) {
if (visited[hs.front() * 2] == -1) {
hs.push(hs.front() * 2);
visited[hs.front() * 2] = visited[hs.front()];
}
else {
if (visited[hs.front() * 2] > visited[hs.front()]) {
visited[hs.front() * 2] = visited[hs.front()];
hs.push(hs.front() * 2);
}
}
}
if (hs.front() > 0) {
if (visited[hs.front() - 1] == -1) {
hs.push(hs.front() - 1);
visited[hs.front() - 1] = visited[hs.front()] + 1;
}
else {
if (visited[hs.front() - 1] > visited[hs.front()] + 1) {
visited[hs.front() - 1] = visited[hs.front()] + 1;
hs.push(hs.front() - 1);
}
}
}
if (hs.front() < 100000) {
if (visited[hs.front() + 1] == -1) {
hs.push(hs.front() + 1);
visited[hs.front() + 1] = visited[hs.front()] + 1;
}
else {
if (visited[hs.front() + 1] > visited[hs.front()] + 1) {
visited[hs.front() + 1] = visited[hs.front()] + 1;
hs.push(hs.front() + 1);
}
}
}
hs.pop();
}
cout << visited[K];
}일단 이 문제의 경우 완전한 백트래킹이라기 보다 백트래킹과 BFS를 섞어서 해야 한다. 이에 나는 일단 BFS에서 주로 사용하는 큐를 작성하였다. 일단 이문제의 경우 BFS를 위해 그냥 계속 영역을 넓혀주면 된다 단 순서상으로 순간이동 즉 *2 부분을 먼저 해주었다. 그후 나머지 +1,-1 부분에서는 내가 접근하는 방식이 최소 방문횟수로 방문했으면 값을 넣어주고 아니면 무시하도록 작성하였다