[13549] 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549

13549 - 숨바꼭질 3

본문

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 $N$($0 \leq N \leq 100000$)에 있고, 동생은 점 $K$($0 \leq K \leq 100000$)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 $X$일 때 걷는다면 1초 후에 $X-1$ 또는 $X+1$로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 $2 \times X$의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 $N$과 동생이 있는 위치 $K$가 주어진다. $N$과 $K$는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

• $0 \leq N, K \leq 100000$

---

풀이

기본적인 숨바꼭질 문제와 똑같이 bfs 탐색을 이용하여 구현한다. 다른 점은 좌우로 움직일 때는 간선이 1이지만, 2배로 움직이는 경우 간선의 가중치는 0이라는 점이다.

기본적인 bfs탐색을 구현하자. 그리고 정점에 도착했을 때, 그 정점을 2배씩 증가시킨 정점 또한 모두 체크하도록 수정하자. 이때 visit을 잘 생각해야하는데, 이미 visit되어 queue에 들어가있어도 2배로 움직이는 정점의 cnt값이 이전에 넣었던 것보다 낮기 때문에, visit체크만 해주고 종료는 따로 하지 않도록 하자. 편법을 쓴다는 느낌이다.

사실 편법을 쓰지 않으려면, visit배열을 int로 지정하여 dp형식으로 정하고, bfs에서의 queue를 일반적인 큐가 아니라 “우선순위 큐”로 구현하면 문제에서 원하는 조건에 부합할 것이다. 근데 범위가 작아서 편법을 써도 구현이 되면, 그냥 넘어가자.. 시간 아끼고 좋은거지 뭐

• 참고 알고리즘 : BFS 탐색

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 30

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
    int pos;
    int cnt;
} ND;

#define MAX_IDX 100000
bool visit[MAX_IDX * 2 + 2];
ND q[MAX_IDX * 2 + 2];
int f, r;
int n, k;

int main() {
    scanf("%d %d", &n, &k);

    visit[n] = true;
    q[r++] = (ND){n, 0};

    while (f < r) {
        ND cur = q[f++];
        for (int i = cur.pos; i <= MAX_IDX * 2; i *= 2) {
            if (i == k) {
                printf("%d", cur.cnt);
                return 0;
            }

            if (i > 0 && visit[i - 1] == false) {
                visit[i - 1] = true;
                q[r++] = (ND){i - 1, cur.cnt + 1};
            }
            if (visit[i + 1] == false) {
                visit[i + 1] = true;
                q[r++] = (ND){i + 1, cur.cnt + 1};
            }

            if (i == 0) {
                break;
            }
        }
    }

    return 0;
}