HyeonSu

취미코딩 하는 개발자

[백준][13549번] 숨박꼭질 3

Updated:

문제 URLPermalink

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

전체 풀이Permalink

수빈이가 할 수 있는행동은 두가지다.

  1. 걷기 : x+1 또는 x-1로 이동(1초)
  2. 순간이동 : 2*x로 이동 (0초)

대부분 bfs 문제는 시간 간격이 1초다. 하지만 0초라는 변형이있다. 이러한 유형은 Dequeue를 사용하여 풀이할 수 있다.

덱을 사용해 순간이동은 dequeue의 앞에, 걷기는 dequeue의 뒤에 넣는 방법도 있다.

dequeue를 사용하지 않는 방법도 있다. 이때 큐는 총 2개가 필요하다 (현재큐/다음큐)

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static int MAX = 100000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] d = new int[MAX + 1];

        Arrays.fill(d, -1);
        Deque<Integer> q = new ArrayDeque<>();
        q.add(n);
        d[n] = 0;

        while (!q.isEmpty()) {
            int x = q.remove();

            if (2 * x <= MAX && d[2 * x] == -1) {
                d[2 * x] = d[x];
                q.addFirst(2 * x);
            }

            if (x - 1 >= 0 && d[x - 1] == -1) {
                d[x - 1] = d[x] + 1;
                q.add(x - 1);
            }

            if (x + 1 <= MAX && d[x + 1] == -1) {
                d[x + 1] = d[x] + 1;
                q.add(x + 1);
            }


        }

        System.out.println(d[k]);
    }
}

다른 풀이 (dequeue)Permalink

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] c = new boolean[MAX];
        int[] d = new int[MAX];
        c[n] = true;
        d[n] = 0;
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
        q.add(n);
        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next : new int[]{now*2, now-1, now+1}) {
                if (next >= 0 && next < MAX) {
                    if (c[next] == false) {
                        c[next] = true;
                        if (next == now*2) {
                            q.addFirst(next);
                            d[next] = d[now];
                        } else {
                            q.addLast(next);
                            d[next] = d[now] + 1;
                        }
                    }
                }  
            }
        }
        System.out.println(d[m]);
    }
}

다른풀이 (queue)Permalink

import java.util.*;

public class Main {
    public static final int MAX = 1000000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        boolean[] c = new boolean[MAX];
        int[] d = new int[MAX];
        c[n] = true;
        d[n] = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> next_queue = new LinkedList<Integer>();
        q.add(n);
        while (!q.isEmpty()) {
            int now = q.remove();
            for (int next : new int[]{now*2, now-1, now+1}) {
                if (next >= 0 && next < MAX) {
                    if (c[next] == false) {
                        c[next] = true;
                        if (now*2 == next) {
                            q.add(next);
                            d[next] = d[now];
                        } else {
                            next_queue.add(next);
                            d[next] = d[now] + 1;
                        }                    
                    }
                }  
            }
            if (q.isEmpty()) {
                q = next_queue;
                next_queue = new LinkedList<Integer>();
            }
        }
        System.out.println(d[m]);
    }
}

Leave a comment

You may also enjoy