백준 [1697] 숨바꼭질

1697번: 숨바꼭질

 

풀이

수빈이가 움직일 수 있는 이동할 수 있는 조건인

한 칸 뒤로 움직일 때 (x-1), 한 칸 앞으로 움직일 때 (x + 1), 순간이동을 하는 경우 (x * 2)로 나누면 현재 위치에서 이동할 수 있는 가장 가까운 노드이므로 BFS 탐색이 효율적일 것 같다고 생각하였다.

 

정답 코드

package com.baekjoon.p1697;

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

public class Main {
    static int[] arr = new int[100001];
    static int n, k;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        bfs(n);
        System.out.println(arr[k]);
    }

    private static void bfs(int val) {
        Queue<Integer> q = new LinkedList<>();

        q.add(val);

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

            if (temp == k) {
                return;
            }

            int back = temp - 1;
            int front = temp + 1;
            int jump = temp * 2;

            if (back >= 0 && arr[back] == 0) {
                q.add(back);
                arr[back] = arr[temp] + 1;
            }
            if (front <= 100000 && arr[front] == 0) {
                q.add(front);
                arr[front] = arr[temp] + 1;
            }
            if (jump <= 100000 && arr[jump] == 0) {
                q.add(jump);
                arr[jump] = arr[temp] + 1;
            }
        }
    }
}

 

Github:

https://github.com/Kim-youngjae/algorithms/blob/764dd61da0d41c6f7ffd578dd56175d356403ba9/src/main/java/com/baekjoon/p1697/Main.java