[백준 BOJ/Silver I] 1697번 : 숨바꼭질

 

정처기 필기와 기술 세미나 준비로 정신없어서 못 풀다가 드디어 다 끝나고!!!!!!!! 오랜만에 푼다

다시 꾸준히 열심히 풀어야겠다💪💪

 

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

1697번: 숨바꼭질

 

- bfs 방식을 이용

- 정해진 숫자에 가장 빨리 닿을 수 있는 경우만 확인하면 되기 때문에 이미 숫자가 채워진 자리는 값을 바꿔주지 않아도 된다

- x-1, x+1, 2*x인 경우를 모두 확인해주어야하며 값이 채워져있지 않다면 이전값에 +1 씩 해주면 된다

- K에 숫자가 들어가면 종료하는데 이때 들어간 숫자에서 1을 빼주어야 답이 된다. 처음에 N으로 시작할때 1을 넣어주고 시작했기 떄문이다.

 

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    static int N;
    static int K;
    static int[] position = new int[100001];
    static int answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        K = Integer.parseInt(str[1]);

        if (N != K) {
            check();
        }

        System.out.println(answer);

    }

    static void check() {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(N);
        position[N] = 1;

        while (!dq.isEmpty()) {
            int x = dq.pollFirst();

            for (int i = 0; i < 3; i++) {
                int nx;
                if (i == 0) {
                    nx = x - 1;
                } else if (i == 1) {
                    nx = x + 1;
                } else {
                    nx = 2 * x;
                }

                if (nx >= 0 && nx < position.length && position[nx] == 0) {
                    dq.addLast(nx);
                    position[nx] = position[x] + 1; // 이전값에 1씩 더해주기
                }
            }

            if (position[K] != 0) {
                answer = position[K] - 1; // 처음값 N 위치를 1로 시작했기 때문에 최종답은 1 빼줘야함
                return;
            }
        }
    }
}