[백준] 1697 숨바꼭질 (JAVA)

✉️문제

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

1697번: 숨바꼭질

 

📝 접근

   최단거리를 구하는 문제이다. DFS로 풀 수 있을 것 같지만, DFS로 구현하면 커팅 기법을 사용해도 지수 시간 복잡도를 가지기 때문에 시간 내에 통과하기 어렵다. 따라서 BFS를 이용해야 한다.

 

🗝 문제풀이

package baekjoon;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class B1697 {

    static int[] ch = new int[100001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 수빈 위치
        int k = sc.nextInt(); // 동생 위치

        BFS(n,k);
        System.out.println(ch[k] - 1); // 방문 표시를 위해 1부터 시작했기 때문에 -1을 해준다.
    }

    public static void BFS(int n, int k) {
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        ch[n] = 1; // 현재 수빈의 위치에 방문 표시를 한다.

        while(!q.isEmpty()) {
            int now = q.poll();

            if(now == k) return;

            int backward = now - 1;
            int forward = now + 1;
            int tele = now * 2;

            // 만약 backward, forward, tele의 값 들을 방문하지 않았다면
            // 방문표시를 하고 queue에 집어 넣는다. 
            if(backward >= 0 && ch[backward] == 0) {
                ch[backward] = ch[now] + 1;
                q.add(backward);
            }

            if(forward <= 100000 && ch[forward] == 0) {
                ch[forward] = ch[now] + 1;
                q.add(forward);
            }

            if(tele <= 100000 && ch[tele] == 0) {
                ch[tele] = ch[now] + 1;
                q.add(tele);
            }
        }
    }
}