ALGORITHM

[JAVA] 백준 1697번- 숨바꼭질

연듀 2023. 1. 9. 21:06

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

 

1697번: 숨바꼭질

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

www.acmicpc.net

 

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

public class Main {
    static int n, k;
    static int answer = 0;
    static boolean[] visited;

    static class Point {
        int v, cnt;

        public Point(int v, int cnt) {
            this.v = v;
            this.cnt = cnt;
        }
    }

    static boolean check(int x) {
        if (x < 0 || x > 100000 || visited[x]) return false;
        return true;
    }

    static void bfs(int v) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(v, 0));
        visited[v] = true;

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            int x = p.v;
            int cnt = p.cnt;

            if (x == k) {
                answer = cnt;
                break;
            }

            if (check(x-1)) {
                queue.add(new Point(x - 1, cnt + 1));
                visited[x - 1] = true;
            }
            if (check(x+1)) {
                queue.add(new Point(x + 1, cnt + 1));
                visited[x + 1] = true;
            }
            if (check(x*2)) {
                queue.add(new Point(x * 2, cnt + 1));
                visited[x * 2] = true;
            }
        }


    }

    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()); // 동생

        // 걸으면 1초후에 x-1 또는 x+1로 이동
        // 순간이동시에는 1초 후에 2*X의 위치로 이동
        visited = new boolean[100001];
        bfs(n);

        System.out.println(answer);
    }
}

 

 

1초 후에 갈 수 있는 좌표 3가지의 경우를 큐에 집어놓고 BFS 탐색을 진행한다.

이 때, 가장 최소 시간을 구해야하므로 이미 방문했던 좌표는 굳이 또 방문하지 않게 하기 위해 visit 배열에다 체크한다.

 

 

'ALGORITHM' 카테고리의 다른 글

[JAVA] 백준 13549번- 숨바꼭질 3  (0) 2023.01.09
[JAVA] 백준 13913번- 숨바꼭질 4  (0) 2023.01.09
[JAVA] 백준 1707번- 이분 그래프  (0) 2023.01.06
[JAVA] 백준 1987번- 알파벳  (0) 2023.01.06
[JAVA] 백준 2580번- 스도쿠  (0) 2023.01.06