[BaekJoon] 17071번 - 숨바꼭질 5 [Java][C++]

문제 링크

---

1. 아이디어

수빈이가 동생을 찾는 최단 시간을 구해야 하는데 동생이 매초 움직이는 상황이다. 수빈이의 이동은 $X - 1$, $X + 1$, $2 \times X$ 총 3가지가 있는데, 이때 한 칸 옆으로 이동했다가 다시 원래 자리로 돌아가면 2초를 소모해서 원래 자리로 돌아올 수 있다는 것이 포인트다. 수빈이가 방문한 좌표들에 대해 홀수 초에 방문했는지 짝수 초에 방문했는지 기록하는 2차원 배열을 활용해서 동생을 매초 이동시키며 수빈이가 방문한 좌표에 동생이 위치할 때 동생과 수빈이 모두 홀수 초거나 짝수 초이면 이는 수빈이가 2의 배수 초만큼 좌우 이동으로 다시 해당 위치로 갈 수 있으므로 동생을 찾을 수 있다는 의미가 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MX = 500_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        System.out.println(bfs(n, k));
    }

    static int bfs(int n, int k) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(n);

        boolean[][] vis = new boolean[1 + MX][2];
        vis[n][0] = true;

        int time = 0;

        while (!q.isEmpty()) {
            int bro = k + time * (time + 1) / 2;
            if (bro > MX) return -1;

            if (vis[bro][time % 2]) return time;

            int nextParity = (time + 1) % 2;
            int sz = q.size();
            while (sz-- > 0) {
                int cur = q.poll();

                int nxt1 = cur - 1;
                if (nxt1 >= 0 && !vis[nxt1][nextParity]) {
                    q.offer(nxt1);
                    vis[nxt1][nextParity] = true;
                }

                int nxt2 = cur + 1;
                if (nxt2 <= MX && !vis[nxt2][nextParity]) {
                    q.offer(nxt2);
                    vis[nxt2][nextParity] = true;
                }

                int nxt3 = cur * 2;
                if (nxt3 <= MX && !vis[nxt3][nextParity]) {
                    q.offer(nxt3);
                    vis[nxt3][nextParity] = true;
                }
            }

            time++;
        }

        return -1;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 500000;
bool vis[1 + MX][2];

int bfs(int n, int k) {
    queue<int> q;
    q.push(n);

    vis[n][0] = true;

    int time = 0;

    while (!q.empty()) {
        int bro = k + time * (time + 1) / 2;
        if (bro > MX) return -1;

        if (vis[bro][time % 2]) return time;

        int nextParity = (time + 1) % 2;
        int sz = q.size();
        while (sz-- > 0) {
            int cur = q.front();
            q.pop();

            for (int nxt : {cur - 1, cur + 1, cur * 2}) {
                if (0 <= nxt && nxt <= MX && !vis[nxt][nextParity]) {
                    q.push(nxt);
                    vis[nxt][nextParity] = true;
                }
            }
        }

        time++;
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    cout << bfs(n, k);
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---