★★★ 백준/13549 숨바꼭질3 / bfs, 다익스트라 알고리즘

숨바꼭질 3

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

59673

17254

11099

25.327%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

5 17

예제 출력 1 복사

2

---

풀이 BFS

BFS 큐에 넣을때 방문처리

//bfs로 먼저 풀이,
//bfs로 풀게되면 곱셈과 덧셈뺄셈의 가중치가 서로 다르기 때문에 가중치 , 즉 비용이 작은것부터 큐에 넣어야한다. 최소비용을 사용해서 도달하는경우를 찾아야하니까.
//비용이 같은 덧셈과 뺄셈의 경우, 비용이 작은 곱셈과 조합해서 사용하였을때 어떤 기호가 더 유용한지 생각해야한다.
//덧셈같은경우 해당숫자+1 의 곱으로 값을 찾게된다. 못찾으면 또 +1 해서 곱셈을 반복해보는.. 즉 원하는 목적지 좌표값을 나눌수있는수를 덧셈으로 찾는것이다.
//그것보다는 뺄셈으로 진행시 점점값이 작아지므로, 목적지 좌표값을 나눌 수 있는 가능성이 훨씬 커진다. 그래서 결과적으로 곱셈,뺄셈,덧셈 순서대로 큐에 넣는다.

우선순위가 높은 값부터 큐에 넣고 , 방문처리를 하므로 해당 위치가 나왔을때가 최소시간이다.(일반적인 bfs)

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,k;
    static final int maxRange = 100000;
    static boolean[] visited = new boolean[maxRange+1];


    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = input[0];
        k = input[1];


    }
    static void solve() throws IOException {
        bfs();
    }
    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int currentPosition = current[0];
            int currentTime = current[1];

            if (currentPosition == k) {
                bw.write(currentTime+"");
                return;
            }

            if (currentPosition * 2 <= maxRange && !visited[currentPosition * 2 ]) {
                visited[currentPosition * 2 ] = true;
                q.add(new int[]{currentPosition * 2 , currentTime});
            }

            if (currentPosition - 1 >= 0  && !visited[currentPosition - 1]) {
                visited[currentPosition - 1] = true;
                q.add(new int[]{currentPosition - 1, currentTime + 1});
            }

            if (currentPosition + 1 <= maxRange && !visited[currentPosition + 1]) {
                visited[currentPosition + 1] = true;
                q.add(new int[]{currentPosition + 1, currentTime + 1});
            }


        }

    }

}

BFS 큐에서 뺄때 방문처리 

큐에 넣을때 방문처리를 하지않고, 큐에서 뺄때 방문처리하니까

4 6 인경우

4가 큐에서 꺼내져서 8,5,3 이 큐에 들어가고

8이 큐에서 나와서 16,9,7 이 큐에 들어가고  5가 큐에서 나와서 10,6,4가 큐에 들어가고

3이 큐에서 나와서 6,4,2가 큐에 들어간다.  넣을때 방문처리를 안하니까 같은 숫자가 큐에 들어갈 수 있게된다.

 

큐에서 뽑았을때 그 수를 방문처리하니까.

나머지 수들은 중복으로 큐에 들어갈 수있다. 

대부분의 경우를 확인하게 되므로 목적지에 도달했을때 최소시간인지 갱신해주는 작업이 필요하다.

[모든경우를 살펴보니까 곱셈,뺄셈,덧셈 아무순서대로 큐에 넣어도 상관없다.]

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n, k,answer;
    static final int maxRange = 100000;
    static boolean[] visited = new boolean[maxRange+1];


    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        answer = Integer.MAX_VALUE;

    }

    static void solve() throws IOException {
        bfs();
        bw.write(answer+"");
    }

    static void bfs() throws IOException {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});
        visited[n] = true;

        while (!q.isEmpty()) {

            int[] current = q.poll();
            int currentPosition = current[0];
            int time = current[1];

            visited[currentPosition] = true;

            if (currentPosition == k) {
                answer = Math.min(answer, time);
            }

            if (currentPosition *2  <= maxRange && !visited[currentPosition*2] ) {
                q.add(new int[]{currentPosition*2, time});
            }

            if (currentPosition + 1 <= maxRange && !visited[currentPosition+1] ) {
                q.add(new int[]{currentPosition+1, time + 1});
            }
            if (currentPosition - 1 >= 0 && !visited[currentPosition-1] ) {
                q.add(new int[]{currentPosition-1, time + 1});
            }


        }

    }


}

모든 경우를 살펴보는것이므로 메모리사용량이 더 크고 시간이 더 오래걸린다.

백준 13549 자바 - 숨바꼭질 3 문제

 

[백준]13549: 숨바꼭질 3 - JAVA

 

 

다른사람풀이

1. 각 위치에 걸리는 시간을 저장한다.

 

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

 

[백준] 13549 : 숨바꼭질 3 (JAVA/자바)

 

 

---

다익스트라

이 문제는 *2이  +1,-1과   가중치가 다르기 때문에  

목표(동생의 위치)까지의 최소 시간을 구하기 위해서는 다익스트라를 사용한다.

 

 /*
    다익스트라를 어떻게 사용할까
    다익스트라는 어떤 위치에서 다른 모든 위치까지의 최소비용을 알 수 있는 알고리즘이다.
    이 문제에서는 시작위치에서 동생위치까지의 최소비용을 알고 싶으니까
    다익스트라로 각 좌표의 위치마다 최소비용을 구하고 마지막으로 동생의 위치의 최소비용값을 출력한다.
     */

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n,k;
    static final int maxRange = 100000;
    static int[] time = new int[maxRange + 1]; //위치별 최소소요시간을 저장할 변수

   
    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);
        Arrays.fill(time, maxRange + 1);
    }

    static void solve() throws IOException {
        dijkstra();
        bw.write(time[k]+"");
    }

    static void dijkstra() throws IOException {
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        pq.add(new int[]{n, 0});
        time[n] = 0;

        while (!pq.isEmpty()) {
            int[] pqPoll = pq.poll();
            int position = pqPoll[0];

            if (time[position] < pqPoll[1]) {
                continue;
            }

            /*
            인접노드를 확인해서 최소거리를 갱신하듯
            현재 위치에서 곱셈,덧셈,뺄셈을 해서 이동할 수 있는 위치를 확인하고 그 위치를 갈 수 있는 최소시간을 갱신해준다. 갱신후 우선순위큐에 넣는다.
             */

            // +1 이동했을때 범위가 넘지않고, 위치+1 로 가는 시간이 원래위치 가는시간 +1초 보다 크다면 갱신시켜준다.
            if (position + 1 <= maxRange && (time[position + 1] > time[position] + 1)) {
                time[position + 1] = time[position] + 1;
                pq.add(new int[]{position + 1, time[position + 1]});
            }
            if (position - 1 >= 0 && (time[position - 1] > time[position] + 1)) {
                time[position - 1] = time[position] + 1;
                pq.add(new int[]{position - 1, time[position - 1]});
            }

            //곱셈이동했을때는 다르다, 다른점은 곱셈시 시간증가가 없다는점
            if (position *2 <= maxRange && (time[position *2] > time[position])) {
                time[position * 2] = time[position];
                pq.add(new int[]{position * 2, time[position * 2]});
            }
            /*
                곱셈이동 예시 들어본다면  1과 2이다. 1은 시작위치므로 0초가 저장되어있고 2는 덧셈을 이용해 최소시간이 1초라고 저장되어있다면
                time[2] > time [1] 이 된다.
                1에서 0초소요되는 곱셈을 이용하면 2가 되기때문에
                time[2] = time[1] 로 갱신해준다.
            */



        }
    }



}

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

 

Baekjoon #13549 숨바꼭질3 (java, 다익스트라, 우선순위큐)