백준 13549 자바 풀이

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

거의 1번 풀이에 가까웠던 3번.

 

[잘못된 풀이]

* 2 를 하는 것이 비용이 가장 적게 들기 때문에 이 방법을 먼저, 많이 체크해주는 것이 중요하다 생각했다. 그래서 Num 이라는 클래스에 n (해당 숫자), dep (깊이), w (가중치 -> *2 한 것이 더 작은 숫자를 가져서 이 기준으로 정렬가능하게)를 넣고, priority queue 를 생성해 compare 함수를 오버라이드 해 w 기준으로 정렬하는 것을 짰다. 하지만 뭔가 값이 계속 틀리게 나와 하나하나 찍어보니 priority queue는 내가 생각했던대로 가중치가 1112222 이런식으로 정렬되는 것이 아니라 힙=이중트리 구조라서 12122212 이런식으로도 찍히더라.. 힙은 맨 앞의 숫자만 이용하고 싶을때 사용하는 게 정확한 것 같다.

 

아무튼 이때부터 감을 잃어서 답을 찾아보니 단순히 *2 하는 연산을 먼저 계산(코드의 윗줄에 넣기)하고 min 변수를 써서 같은 뎁스 안에 들어온 K라면 누가 *2를 더 많이 썼는지(시간이 가장 적게 걸린) 확인후 갱신해 min값을 출력하면 되는 것이었다. 중간에 return을 해주지 않기 때문에 시간이나 메모리는 더 많이 쓰는 것 같지만, 답이 정확하게 맞으려면 이렇게 작성해야 했다. 더 짧은 시간내에 리턴할 수 있는 방법이 있는지 알아봐야 할 것 같다.

• 큐에서 뺄 때 방문체크를 하자. -> 그래야 같은 뎁스에 있는 같은 목표하는 숫자(K)를 큐에 넣을 수 있음. -> 그래야 누가 빠른지 비교가능.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class bj13549 {

    public static class Num {
        int n, dep;

        public Num(int n, int dep) {
            this.n = n;
            this.dep = dep;
        }
    }

    static int N, K;
    static boolean[] visit;
    static int min = Integer.MAX_VALUE;

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        visit = new boolean[100001];

        if (N >= K) {
            System.out.println((N - K));
            return;
        }

        BFS();

        System.out.println(min);

    }

    private static void BFS() {
        Queue<Num> q = new LinkedList<>();

        Num start = new Num(N, 0);

        q.offer(start);

        while (!q.isEmpty()) {
            Num cur = q.poll();
            visit[cur.n] = true;

            if (cur.n == K) min = Math.min(cur.dep, min);

            int next = cur.n * 2;
            if(next < visit.length && !visit[next]) {
                q.offer(new Num(next, cur.dep));
            }

            next = cur.n + 1;
            if(next < visit.length && !visit[next]) {
                q.offer(new Num(next, cur.dep + 1));
            }

            next = cur.n - 1;
            if(next >= 0 && !visit[next]) {
                q.offer(new Num(next, cur.dep + 1));
            }

        }
    }


}