(17071) 숨바꼭질 5 (Java)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

예제 입력 1

5 17

예제 출력 1

2

예제 입력 2

17 5

예제 출력 2

4

예제 입력 3

6 6

예제 출력 3

0

예제 입력 4

1 500000

예제 출력 4

-1

예제 입력 5

250000 499999

예제 출력 5

1

예제 입력 6

1 10

예제 출력 6

6

출처

문제를 만든 사람: baekjoon
데이터를 추가한 사람: dlwocks31, kravi

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색

Solution

1 메모리 초과

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int n, k;
    public static int[] dx = {2, -1, 1};
    public static Queue<Node> q;
    public static class Node {
        int x, time;
        Node(int x, int time) {
            this.x = x;
            this.time = time;
        }
    }

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

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

        q = new LinkedList<Node>();
        q.offer(new Node(n, 0));

        bw.write(String.valueOf(findBro()));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int findBro() {
        int cnt = 0;
        while(!q.isEmpty()) {
            cnt++;

            int size = q.size();

            for(int i = 0; i < size; i++) {
                Node cur = q.poll();

                // 동생을 찾은 경우 시간 return
                if(cur.x == k) return cur.time;

                for(int j = 0; j < 3; j++) {
                    int nx;
                    if(j == 0) {
                        nx = cur.x * dx[j];
                    } else {
                        nx = cur.x + dx[j];
                    }

                    if(isNotRange(nx)) continue;

                    q.offer(new Node(nx, cur.time+1));
                }
            }
            // 동생이 맵을 벗어나면 못찾으므로 return -1
            if(k >= 500000) return -1;
            // 동생 이동
            k += cnt;
        }

        return -1;
    }

    public static boolean isNotRange(int x) {
        return (x < 0 || x >= 500001) ? true : false;
    }
}

2

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int n, k;
    public static boolean visited[][];
    public static int[] dx = {2, -1, 1};
    public static Queue<Integer> q;

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

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

        q = new LinkedList<Integer>();
        visited = new boolean[2][500001];

        q.offer(n);
        visited[0][n] = true;   // 0초 방문 체크

        bw.write(String.valueOf(findBro()));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int findBro() {
        if(n == k) return 0;

        int size, flag, time = 0;

        while(!q.isEmpty()) {
            size = q.size();
            time++;
            flag = time % 2;    // 짝수초는 0, 홀수초는 1

            // 동생 이동
            k += time;
            // 동생이 맵을 벗어나면 못찾으므로 return -1
            if(k > 500000) return -1;
            
            for(int i = 0; i < size; i++) {
                int cur = q.poll();

                for(int j = 0; j < 3; j++) {
                    int nx;
                    if(j == 0) {
                        nx = cur * dx[j];
                    } else {
                        nx = cur + dx[j];
                    }

                    if(isNotRange(nx) || visited[flag][nx]) continue;

                    q.offer(nx);
                    visited[flag][nx] = true;
                }
            }

            // 동생이 있는 위치가 방문되었다면
            if(visited[flag][k]) return time;
        }

        return -1;
    }

    public static boolean isNotRange(int x) {
        return (x < 0 || x >= 500001) ? true : false;
    }
}

Feedback

1. 수빈이가 동생보다 먼저 특정 지점에 도착하게 되면 이미 방문처리가 되었기 떄문에 둘은 만날 수가 없게된다는 문제가 있어, 방문처리를 아예 하지 않도록 하였다. 그랬더니 메모리 초과의 문제가 발생하였다... 시간초과는 이해가 가겠는데, 왜 메모리 초과가 나는 것인지는 잘 모르겠다..
   (시간복잡도와 공간복잡도에 대한 공부가 더 필요하다.)

2. 한 가지 규칙이 있다. 수빈이가 어떤 특정한 지점을 x초에 방문했다면 x+2, x+4, x+6...초 후에도 해당 지점을 방문할 수 있다는 것이다. 특정 지점에서 +1 이동 후 -1 이동하거나, -1 이동 후 +1 이동하는 경우가 그렇다.

따라서 짝수초에 이미 y 지점을 방문했다면, 해당 위치는 큐에 다시 넣어 탐색할 필요없이 visited[0][y] = true로 방문처리만 해놓는다면, 이후 짝수초에서는 해당 위치를 방문한 적이 있는지만 체크하면 될 것이고, 이때 해당 위치에 동생이 오게된다면 계속 카운트하고 있던 시간을 리턴해줌으로써 동생을 찾게되는 시간을 구할 수 있다.