영원히 남는 기록, 재밌게 쓰자

백준 [1697] 숨바꼭질 본문

Algorithm/백준

백준 [1697] 숨바꼭질

youngjae-kim 2024. 2. 7. 00:03
728x90
반응형
 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

풀이

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

한 칸 뒤로 움직일 때 (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

728x90
반응형

'Algorithm > 백준' 카테고리의 다른 글

백준 [13913] 숨바꼭질 4  (0) 2024.02.21
백준 [15651] N과 M (3)  (0) 2024.02.18
백준 [15650] N과 M (2)  (0) 2024.02.18
백준 [15649] N과 M (1)  (2) 2024.02.18
백준 [7576] 토마토 (JAVA)  (0) 2024.02.14