[JAVA] 백준 1697번 숨바꼭질

1) 문제

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

2) 접근 방법

예전에 한 번 풀어보긴 했었는데 기억은 나지 않았다.
스터디에서 숙제로 나온 문제였는데 이게 BFS 문제라는데,,
실은 문제를 읽으면서 뭔가 DP같은 느낌이 들었는데, BFS로 풀어보려 했으나.. BFS인 게 잘 와닿지 않았다.
결국.. 또 다른 분의 풀이를 봐버리고 이해하면서 진행했다..

이 문제는 DP로도 풀 수 있고 1차원 BFS 문제이다.

그런데 왜 BFS일까?

+) 출처 : https://hongjw1938.tistory.com/133

이 문제는 -1, +1, *2 모든 시점에 대해 시간 가중치가 1인 문제로 바라볼 수 있다.
예전에 이코테 책을 공부했을 때, 가중치가 1인 경우에 대해서는 BFS를 이용하면 좋다고 하는 팁이 있었다. 까먹음..

현재 정점에서 이동 가능한 경우 (-1, +1, *2 )의 경우를 모두 체크한 뒤 탐색을 시작하고,
해당 탐색 위치가 동생의 위치라면 탐색을 중지하면 된다고 한다.

큐를 만들어서 현재 이후 다음 탐색 위치를 큐에 넣으면 된다.
visited[] 배열에 대해서는 현재 몇 초가 지났는지를 넣으면 된다.

코드 출처 : https://smartpro.tistory.com/18

3) 코드

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

public class Main {

    static int n, k, subin, cnt;
    static int[] visited;
    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());
        visited = new int[100001];

        subin = n;
        cnt = 1; // 배열의 기본값이 0이므로 첫 위치 시간을 1로 잡음
        System.out.println(run(subin));
    }

    static int run(int subin) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(subin);
        visited[subin] = 1;

        while (!q.isEmpty()) {
            int now = q.poll();
            if (now == k) {
                return visited[now] - 1;
            }

            if (now - 1 >= 0 && visited[now - 1] == 0) {
                visited[now - 1] = visited[now] + 1;
                q.offer(now - 1);
            }

            if (now + 1 <= 100000 && visited[now + 1] == 0) {
                visited[now + 1] = visited[now] + 1;
                q.offer(now + 1);
            }

            if (now * 2 <= 100000 && visited[now * 2] == 0) {
                visited[now * 2] = visited[now] + 1;
                q.offer(now * 2);
            }
        }

        return -1;
    }
}