자바(백준) 13549 숨바꼭질 3

오답 노트 & 새로 알게 된 점

이번 문제는 18번의 시도 끝에 AC를 받았다.

문제 풀이 방법 : bfs를 사용한 풀이, 다익스트라를 사용한 풀이

 

처음에는 최소 시간 구하라해서 bfs를 이용하면 되겠다라는 생각으로 쉽게 생각했다.

하지만 보통이 아닌 문제였다.

 

코드1

코드1에서 중요한 점은 *2를 할 때의 while문이다.

문제에서 *2를 하게 되면 cnt를 늘리지 않는다. 

즉, 최소 시간을 구해야하기에 범위가 넘지 않고, 방문을 하지 않았다면

2배에서 끝내지 않고, 4배 8배 16배 계속 해줘야하는 것이다.

왜?

최소 시간을 구해야하고, *2는 cnt를 늘리지 않기 때문이다.

 

지금 if문의 순서가 *2, -1, +1 순서로 되어있지만, *2가 -1이나 +1의 뒤에 가게 된다면 틀리게 된다.

그 이유는 아래의 링크를 통해 이해하면 된다.

https://www.acmicpc.net/board/view/38887#comment-69010

글 읽기 - [13549-숨바꼭질3] BFS 큐에 넣는 순서 질문

 

코드2

bfs는 가중치가 모두 1인 그래프에서 사용할 수 있고, 

이 문제는 가중치가 0과 1로 이루어져 있어, 가중치 >= 0 일 때 사용하는 최소 경로를 판단하는 

다익스트라 알고리즘을 사용하면 된다. 

 

다익스트라에서 가장 중요한 

time 배열을 MAX_VALUE로 초기화 시켜주고, info.cnt 값과 비교하여 time배열 값이 더 크다면 값을 바꿔줘야한다.

 

시작점은 0으로 해야한다는 것을 잊어버려서 한 번 틀리게 됐다.

문제에서 자기 자신한테는 갈 수 없으므로 즉, N == K 가 같아지면 0이 나와 

시작점은 0으로 해줘야한다.

 

---

코드1 - bfs 사용

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N,K;
    static boolean visit[];
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        Queue<Info> q = new ArrayDeque<>();
        q.offer(new Info(N, 0));
        visit[N] = true;
 
        while (!q.isEmpty()) {
            Info info = q.poll();
 
            if(info.x == K){
                min = Math.min(min, info.cnt);
                continue;
            }
 
            //아래 두 if문을 이 위치로 해놓으면 틀리다가 나옴
 
            int num = info.x;
            while (isRangeTrue(num * 2)) {
                if (!visit[num * 2]) {
                    q.offer(new Info(num * 2, info.cnt));
                    visit[num * 2] = true;
                }
                else break;
                num *= 2;
            }
 
            if(isRangeTrue(info.x + 1) && !visit[info.x + 1]){
                q.offer(new Info(info.x + 1, info.cnt + 1));
                visit[info.x + 1] = true;
            }
            if(isRangeTrue(info.x - 1) && !visit[info.x - 1]){
                q.offer(new Info(info.x - 1, info.cnt + 1));
                visit[info.x - 1] = true;
            }
 
        }
 
        System.out.println(min);
 
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
        visit = new boolean[100001];
    }
 
    static boolean isRangeTrue(int x) {
        return x >= 0 && x <= 100000;
    }
 
    static class Info{
        int x, cnt;
 
        public Info(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
    }
}
 

 

코드2 - 다익스트라 사용

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N,K;
    static int time[];
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
 
        for (int i = 0; i <= 100000; i++) time[i] = Integer.MAX_VALUE;
 
        PriorityQueue<Info> pq = new PriorityQueue<>((o1, o2)->{
            return o1.compareTo(o2);
        });
 
        pq.offer(new Info(N, 0));
        time[N] = 0;
 
        while (!pq.isEmpty()) {
            Info info = pq.poll();
 
            if(isRangeTrue(info.x + 1) && time[info.x + 1] > info.cnt + 1){
                time[info.x + 1] = info.cnt + 1;
                pq.offer(new Info(info.x + 1, info.cnt + 1));
            }
 
            if(isRangeTrue(info.x - 1) && time[info.x - 1] > info.cnt + 1){
                time[info.x - 1] = info.cnt + 1;
                pq.offer(new Info(info.x - 1, info.cnt + 1));
            }
 
            if(isRangeTrue(info.x * 2) && time[info.x * 2] > info.cnt){
                time[info.x * 2] = info.cnt;
                pq.offer(new Info(info.x * 2, info.cnt));
            }
 
        }
 
        System.out.println(time[K]);
 
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        K = atoi(st.nextToken());
        time = new int[100001];
    }
 
    static boolean isRangeTrue(int x) {
        return x >= 0 && x <= 100000;
    }
 
    static class Info implements Comparable<Info>{
        int x, cnt;
 
        public Info(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
 
        @Override
        public int compareTo(Info o) {
            return this.cnt - o.cnt;
        }
    }
}