[백준] 1697 숨바꼭질 1차원 BFS

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

1697번: 숨바꼭질

 

 

문제풀이

1차원 BFS이다.

2차원 BFS의 check 변수를 node로 사용한다.

 

 

제출코드

package baekjoon;

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

public class Main1697 {

    static int length = 100000;
    static int[] node = new int[length+1];
    static Queue<Integer> queue = new LinkedList<>();
    static int goal;

    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        int start = scan.nextInt();
        goal = scan.nextInt();

        int time = bfs(start)-1;
        System.out.println(time);
    }

    private static int bfs(int start) {
        queue.offer(start);
        node[start] = 1;   //0초로 하면 방문했는지 알 수 없기때문에 1초로 기재하고, 결과값에서 -1 하기로한다

        while(!queue.isEmpty()){
            int temp = queue.poll();
            //System.out.print("time : " + node[temp] + ", 현재노드 : " + temp + ", 방문노드 : ");

            //움직일 수 있는 방법의 가지 수
            int index = 0;
            for (int i = 0; i < 3; i++) {
                switch (i){
                    case 0 : index = temp-1; break;
                    case 1 : index = temp+1; break;
                    case 2 : index = temp*2; break;
                }

                if(index >=0 && index <= length && node[index] == 0){  //방문하지 않은 곳이라면
                    //node[index] == 0 만 했더니 ArrayIndexOutOfBounds가 발생했다.
                    // index >=0 && index <= length 를 뒤에 붙여주어도 동일하게 오류가 발생했다.
                    queue.offer(index);
                    node[index] = node[temp] + 1;
                }
                //System.out.print(index + ", ");

                if(index == goal){
                    return node[index];
                }
            }
            //System.out.println();
        }
        return 0;
    }

}