b1697_숨바꼭질

 

1697번: 숨바꼭질

package com.hotfive.workbook.b1697_숨바꼭질;

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

public class Main {
    static int V;
    static int second;
    static int [] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt(); //0 ≤ N ≤ 100,000
        int K = sc.nextInt(); //0 ≤ K ≤ 100,000
        second = 0;
        visited = new int[100001]; // index가 위치, 값은 second
        if(V!=K) bfs(V,K);

        System.out.println(second);
        sc.close();
    }

    private static void bfs(int v, int k) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v]++;
        //System.out.println(v + " "+visited[v]);
        while (!queue.isEmpty()){
            v = queue.poll();

            int next = 0;
            for (int i = 0; i < 3; i++) {
                switch (i){
                    case 0 : next = v + 1;
                        break;
                    case 1 : next = v - 1;
                        break;
                    case 2 : next = v * 2;
                        break;
                }
                if(next>=0 && next <=100000 && visited[next]==0) {
                    visited[next] = visited[v] + 1; // 이동전의 시간 + 1

                    if(next == k){
                        second = visited[next]-1;
                        return;
                    }
                    queue.add(next);
                }

                //System.out.println(next + " "+visited[next]);
            }

        }
    }
}

이동하는 위치를 index로 가지는 배열을 만들어서 BFS를 실행하였다.

이동하는 방법은 3가지이기 때문에 세가지 전부 해봐야한다. 그래서 for문으로 세번 반복하게끔 처리하였다.

배열에 해당 위치마다 몇초가 지났는지 알 수 있게끔 값을 저장하고, 한번 이동할 때마다 1씩 증가하게끔 이동 전의 시간 + 1 을 해주었다.

주의: 배열을 사용하기 때문에 다음 이동하는 위치가 ArrayIndex 벗어나지 않게 next>=0 && next <=100000 로 처리해줘야한다.