[백준] no13549: 숨바꼭질 3

문제

    /**

     * 주어진 두개의 숫자 중,

     * 시작 숫자가 목표숫자에 도달할 때까지 걸리는 시간을 출력하기

     * 조건1. 1초에 +1 or -1가능

     * 조건2. 시간 추가없이 *2 무한정 가능

     */

문제 링크 : https://www.acmicpc.net/problem/13549

---

원리

BFS를 이용한 풀이

             * 0. 현재숫자 == 목표숫자면 종료

             * 1. -1을 수행, sec++  => 반복

             * 2. +1을 수행, sec++  => 반복

             * 3. *2를 수행         => 반복

---

풀이방법

일반적인 BFS 방식으로 풀 경우 백준 내 채점 중 8% 혹은 12% 정도에서 틀린다

핵심1 : 범위를 지정하는 부분

핵심2 : 대기열 중 제일 먼저 도달한 객체가 꼭 제일 최소한의 시간으로 도달하는 것이 아니라는 점

---

나의 코드

BFS를 이용한 경우의 수 탐색 : 모든 경우의 수를 탐색해야한다. 따라서 메모리상 visited는 필수다.

import java.util.*;
import java.io.*;

public class no13439 {
    /**
     * 주어진 두개의 숫자 중,
     * 시작 숫자가 목표숫자에 도달할 때까지 걸리는 시간을 출력하기
     * 조건1. 1초에 +1 or -1가능
     * 조건2. 시간 추가없이 *2 무한정 가능
     */

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static boolean[] visited = new boolean[2000001]; // 둘다 최대는 100000이므로;
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int sb = Integer.parseInt(st.nextToken());
        int goal = Integer.parseInt(st.nextToken());

        if(sb==goal) System.out.println(0);  // 수빈이랑 목표지점이 애시당초 같을 경우
        else if (sb>goal) System.out.println(sb-goal); // 수빈이가 목표지점보다 더 클경우, 선택지는 -1밖에 없다.
        else System.out.println(calcul(sb, goal)); // 그 외
    }    

    private static int calcul (int sb, int goal) {
        Deque<Subin> dq = new ArrayDeque<>();
        dq.add(new Subin(sb, 0));
        int result = Integer.MAX_VALUE;
        
        while(!dq.isEmpty()) {
            Subin subin = dq.poll();

            // 현재 위치를 방문 표시한다. 만약 대기열에 넣을때 방문 표시를 하게되면, 아래 -1, +1, *2 연산이 이루어 지지 않는다.
            visited[subin.Now] = true; 

            // 목표지점에 도달하더라도, 나머지를 전부 확인해서 가장 최소의 시간을 구해야 한다. (while반복 break안함)
            if(subin.Now == goal && result>=subin.Sec) result = subin.Sec; 
            
            // 각 조건별로 케이스를 만들어 대기열에 넣는다.
            // -1의 경우, 0보다 작아지면 안되는 것을 주의
            // +1이나 *2의 경우, 100000보다 커지면 안되는 것을 주의
            if(subin.Now-1 >= 0 && !visited[subin.Now-1]) dq.add(new Subin(subin.Now-1, subin.Sec+1));  // -1의 경우
            if(subin.Now+1 <= 100000 && !visited[subin.Now+1]) dq.add(new Subin(subin.Now+1, subin.Sec+1));  // +1의 경우
            if(subin.Now*2 <= 100000 && !visited[subin.Now*2]) dq.add(new Subin(subin.Now*2, subin.Sec)); // *2의 경우
        }
        return result;
    }

    private static class Subin {
        private int Now;
        private int Sec;

        public Subin (int now, int sec) {
            this.Now = now;
            this.Sec = sec;
        }
    } 
}

---

레퍼런스 코드

레퍼런스 코드의 경우, 조건문에서 visited에 대한 조건을 시간(time)과 연결지어 사용함으로써,

메모리와 실행시간을 단축시킬 수 있었던 것 같다.

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

public class Main {
    static class Loc{
        int idx;
        int time;

        public Loc(int idx, int time) {
            this.idx = idx;
            this.time = time;
        }
    }

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

        int n = Integer.parseInt(inputs[0]); // 수빈이의 위치
        int k = Integer.parseInt(inputs[1]); // 동생의 위치

        int[]  visited = new int[100001];

        Queue<Loc> q = new LinkedList<>(); // location(위치) 저장
        q.add(new Loc(n, 1)); // 시작 time을 1로 해놓고, 결과 출력시 1 빼기. visited의 값이 0인 것(방문 안한 곳)과 구별해주기 위해서.
        visited[n] = 1; 

        while (!q.isEmpty()) {
            Loc now = q.poll();
            
            // 이렇게 쓰면 틀림
//            if(now.idx==k) {
//                visited[now.idx] = now.time;
//                System.out.println(now.time-1);
//                break;
//            }

            if(now.idx+1>=0 && now.idx+1<=100000){ // 앞으로 한칸
                if(visited[now.idx+1] == 0 || visited[now.idx+1] > now.time+1){
                    visited[now.idx+1] = now.time+1;
                    q.add(new Loc(now.idx + 1, now.time + 1));
                }
            }

            if(now.idx-1>=0 && now.idx-1<=100000){ // 뒤로 한칸
                if(visited[now.idx-1] == 0 || visited[now.idx-1] > now.time+1) {
                    visited[now.idx - 1] = now.time + 1;
                    q.add(new Loc(now.idx - 1, now.time + 1));
                }
            }

            if(now.idx*2>=0 && now.idx*2<=100000){ // 순간이동
                if(visited[now.idx*2] == 0 || visited[now.idx*2] > now.time) {
                    visited[now.idx*2] = now.time;
                    q.add(new Loc(now.idx*2, now.time));
                }
            }

        }

        System.out.println(visited[k]-1);



    }
}

참고 링크 : https://velog.io/@yanghl98/%EB%B0%B1%EC%A4%80-13549-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88-3-JAVA%EC%9E%90%EB%B0%94