백준 1697 번: 숨바꼭질 (java)

 

문제

 

1697번: 숨바꼭질

난이도 : 실버 1

유형 : 그래프, BFS

 

접근법

 

1. 방문여부와 이동시간를 저장하는 배열 check 변수를 100,001의 범위로 생성한다. 이 변수를 이용해 이전이동값에서 +1 하는 방식으로 이동시간을 측정한다.

2. 큐에 처음위치를 추가하고, 큐에서 하나의 요소를 꺼낼때마다 해당요소에 +1, -1, *2 연산의 값을 큐에 저장한다. 이때 연산값은 0이상 100,001 이하 check[연산값] == 0 로 범위와 방문여부를 체크한다.

3. 반복중 다음 연산값이 목표값 K와 같다면 이동시간을 출력하고 반복을 멈춘다.

 

풀이

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 BOJ1697 {
    static int N, K;
    static int check[] = new int[100001];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if(N == K){
            System.out.println(0);
        }else {
            BFS(N);
        }
    }
    static void BFS(int start){
        Queue<Integer> qu = new LinkedList<>();
        qu.add(start);
        check[start] = 1;

        while(!qu.isEmpty()){
            int current = qu.poll();

            for(int i=0; i<3; i++){
                int next;

                if(i == 0) {
                    next = current + 1;
                }else if(i == 1){
                    next = current - 1;
                }else{
                    next = current * 2;
                }

                if(next == K){
                    System.out.println(check[current]);
                    return;
                }

                if(next >= 0 && next < check.length && check[next] == 0){
                    qu.add(next);
                    check[next] = check[current] + 1;
                }
            }
        }
    }
}