[백준] 1697 숨바꼭질 - JAVA

이번 문제는 오랜만에 1차원 배열을 이용한 그래프 순회 문제이다.

처음 이 문제를 봤을 때는 그래프 순회 문제가 아닌 수식 문제인줄 알았는데 수식보다 bfs로 푸는게 나을 것 같다.

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[] arr;
    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());
        arr = new int[100001];

        if(N==K){
            System.out.println(0);
        } else {
        bfs(N);
        }
    }
    private static void bfs(int N) {
        Queue<Integer> q = new LinkedList<>();
        q.add(N);
        arr[N] = 1;
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i=0; i<3; i++){
                int next;
                if(i==0){
                    next=cur + 1;
                }
                else if(i==1){
                    next=cur-1;
                }
                else{
                    next=cur*2;
                }
                if(next==K){
                    System.out.println(arr[cur]);
                    return;
                }
                if(next>0 && next < arr.length && arr[next]==0){
                    q.add(next);
                    arr[next] = arr[cur] + 1;
                }
            }
        }
     }
}

문제가 짧은 만큼 알고리즘은 단순하다.

queue를 활용한 bfs 탐색을 진행한다.

1. queue에서 요소를 하나 뺀다.(초기 위치(N)이 처음에는 들어가있다.)

2. +1, -2, *2를 했을 때 위치를 검사한다

2-1. 만약 목표 위치를 찾았다면 출력하고 종료한다.

2-2. 목표 위치가 아니고 방문한 적 없으면서 1~100000 사이의 위치면 queue에 넣고 1번으로 돌아간다.