백준 P13549 숨바꼭질3 Java 자바

문제

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

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

입력

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

출력

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

시간 초과 -> 메모리 초과 -> 틀림 -> 맞음

순으로 되었다. 물론 이 앞에는 틀렸습니다가 무수히 많다   

풀이

완전탐색으로 현재위치에 *2, +1, -1 한 값들에 대해 탐색을 한다.

1. N이 K보다 클 경우 -1 만 하면 되고, N >= K 이 되면 종료한다. (N>K일 경우 -1해야하는 갯수만 추가)

시간 초과

처음 완전탐색을 dfs로 풀어 시간 초과가 났다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int count;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        if(N>=K){
            count = N-K;
            System.out.println(count);
            return;
        }
        count = K - N; // (+)만 한 경우로 초깃값 설정. 
        bfs(N, K, 0);
        System.out.println(count);
    }

    private static void bfs(int start, int end, int cnt) {
    // (-), (+) 만 반복할 수 있으니 cnt 갯수에 대한 종료문 추가
        if(cnt>count){
            return;
        }
        if(start<0 || start>100000){
            return;
        }
        if(start >= end){
           count = Math.min(count, cnt + start - end);
            return;
        }

        bfs(start+1, end, cnt+1);
        bfs(start-1, end, cnt+1);
        bfs(start *2, end, cnt);
    }
}

메모리 초과

시간 초과가 나서 큐를 이용한 bfs 탐색으로 수정했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int count;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<int[]> qp = new LinkedList<>();
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        if(N>=K){
            count = N-K;
            System.out.println(count);
            return;
        }
        count = K-N;
        qp.add(new int[]{N,0});
        while (!qp.isEmpty()){
            int[] poll = qp.poll();
            if(poll[1] > count || poll[0]<0 || poll[0]>100000){
                continue;
            }
            if(poll[0] >= K){
                count = Math.min(count, poll[1] + poll[0] - K);
                continue;
            }
            qp.add(new int[]{poll[0]+1, poll[1]+1});
            qp.add(new int[]{poll[0]-1, poll[1]+1});
            qp.add(new int[]{poll[0]*2, poll[1]});
        }
        System.out.println(count);
    }

}

반복되는 값이 많다보니 메모리 초과가 났다.
근데 방법을 몰라 검색해보니 이미 온 곳을 체크해 주어야 했다..!
오
cnt가 적은 순으로 탐색하다 보니 이미 온 곳은 탐색할 필요가 없는거였다.
예시 ) 출발점이 2일 때, 이미 *2로 0초만에 4로 다녀갔는데, 나중에 +1, +1로 와봤자 돌아오는 것 뿐이다.

그래서 이제 다녀간 곳을 체크해주는 코드를 추가해주었다.

틀렸습니다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int count;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<int[]> qp = new LinkedList<>();
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        if(N>=K){
            count = N-K;
            System.out.println(count);
            return;
        }
        count = K-N;
        qp.add(new int[]{N,0});
        boolean [] visited = new boolean[100001];
        while (!qp.isEmpty()){
            int[] poll = qp.poll();

            if(poll[1] > count || poll[0]<0 || poll[0]>100000){
                continue;
            }
                 if(visited[poll[0]]){
                continue;
            }
            visited[poll[0]]=true;
            if(poll[0] >= K){
                count = Math.min(count, poll[1] + poll[0] - K);
                continue;
            }

            qp.add(new int[]{poll[0]+1, poll[1]+1});
            qp.add(new int[]{poll[0]-1, poll[1]+1});
            qp.add(new int[]{poll[0]*2, poll[1]});

        }
        System.out.println(count);
    }

}

이렇게 하니 틀려서 보니 (보니하니?푸하핫..) 큐에 값을 넣는 순서가 *2가 마지막인데 먼저 넣어주어야했다.
cnt 값이 가장 작으니 먼저 넣어주어야 한다.

--> 시작점이 1일 때 +1을 하면 2가 되고 다녀간 값으로 체크된다. 시간은 ==1초걸림
이때 *2로 가면 2가 되고, 시간은 == 0초이다. 하지만 2가 다녀간 것으로 체크되어 무시된다.

그래서 *2를 먼저 해주었는데 또 틀렸다.

정답 코드

기존 값의 유효성 상관없이 큐에 넣고 나중에 검사를했다. 값의 범위 체크, 방문여부 체크
--> 큐에 넣기 전 유효성 체크를 해주었다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int count;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<int[]> qp = new LinkedList<>();
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        if(N>=K){
            count = N-K;
            System.out.println(count);
            return;
        }
        count = K-N;
        qp.add(new int[]{N,0});
        boolean [] visited = new boolean[100001];
        while (!qp.isEmpty()){
            int[] poll = qp.poll();
            if(poll[0] >= K){
                count = Math.min(count, poll[1] + poll[0] - K); 
            }else{
              if(poll[0]*2>=0 && poll[0]*2<=100000 && !visited[poll[0]*2]){
                  qp.add(new int[]{poll[0]*2, poll[1]});
                  visited[poll[0]*2]=true;
              }
              if(poll[0] - 1 >= 0 && !visited[poll[0] - 1]){
                  qp.add(new int[]{poll[0]-1, poll[1]+1});
                  visited[poll[0]-1]=true;
              }
              if(poll[0]+1<=100000 && !visited[poll[0]+1]){
                  qp.add(new int[]{poll[0]+1, poll[1]+1});
                  visited[poll[0]+1]=true;
              }
            }
        }
        System.out.println(count);
    }

}

그런데 유효성 검사를 나중에 하면 왜 안되는지 모르겠다..

이 글을 쓰게 된 이유이기도 한데 아시는분 있으면 알려주세요 감사합니다.

알게 되면 추가 하겠습니다 ^--^

추가

알고리즘 스터디를 시작하게 되고 팀원분이 문제를 알아내셨는데
유효성 검사의 순서가 중요한 것이 아니라 큐에 *2, +1, -1 순으로 넣은 순서가 문제였다.

출발지 : 4 , 도착지 : 6 인 반례를 찾아주셨다.

큐에 들어가는 순으로 *2 , +1, -1 한 값인 8, 5, 3이 먼저 처음 들어간다.
그리고 5를 먼저 계산하게 되면서 +1을 해주고 시간은 2초가 걸려 6에 도착하게 되서 6은 방문한 것으로 체크되게 된다.
이후에 3이 *2하여 총 시간 1초만에 6에 도착하게 되지만 이미 방문체크가 되어 누락된다.

그래서 결론은 PriorityQueue를 이용하여 count가 작은 순으로 먼저 계산을 할 수 있게 해주어야 한다.

혹은 여기서는 그대로 Queue를 쓰고 -1계산을 먼저 해주는 것만으로도 가능하다고 생각한다.
-1을 먼저해서 *2를 해 먼저 도착지점에 빠르게 가능 경우는 있어도 , +1로 가야 빠른 경우에는 어차피 -1한 값은 더 느리게
도착하게 될 것이기 때문이다.

하지만 모든 경우에 완벽하고 깔끔하게 하려면 priroityQueue를 쓰는 것이 가장 안정적인 방법인 것 같다.

문제 해결 완료 ~~