백준 1697 숨바꼭질 문제 자바 JAVA BFS 알고리즘 풀이

 

백준 1697 숨바꼭질 문제는 BFS 알고리즘을 사용해서 풀어보는 문제다. 술래의 위치에서 동생이 숨어있는 위치까지 이동하기 위한 횟수를 계산하게 된다. 술래는 좌,우,*2 순간이동을 할 수 있다고 가정한다. 동생의 위치까지 도착하기 위한 최단시간은 얼마인지를 구하기 위해서는 이동한 모든 노드에 대해서 COUNT를 해야 한다.

 

BFS 알고리즘 이해하기

 

백준 7569 토마토 3D 알고리즘 문제 자바 JAVA 풀이 해설 리뷰

 

백준 7576 토마토 알고리즘 문제 자바 JAVA CODE

 

백준 1012 유기농 배추 알고리즘 자바 JAVA

 

 

술래와 동생의 위치는 1차원 좌표값이지만, 이진 트리로 생각해보면 쉽게 답을 얻을 수 있다. 주어진 문제에서 입력값은 5에서 출발한다. 자식 노드는 4,6,10이 된다. 4의 값으로 이동하면 3,5,8을 자식노드로 얻는다. 6으로 이동하면 5,7,12를 자식노드로 얻게 된다. 10의 위치로 이동하면 9,11,20의 자식노드를 얻게 된다.

 

 

 

문제 풀이

 

백준 1697 문제를 풀기 위해서는 이동할 때마다 COUNT를 할 수 있는 배열과 자식노드의 모든 요소를 검색할 수 있는 알고리즘은 BFS가 필요하다. 5에서 시작한 동생을 찾는 과정은 4번에 걸쳐 17에 도달하게 된다. 배열의 크기는 문제에서도 주어지지만 100,000이하의 정수로 주어진다.

 

 

백준 1697 자바 풀이 일러스트레이트

 

 

 

백준 1697 숨바꼭질 JAVA 자바 CODE

/*
    Owner : Developer Blog
    Title : 숨바꼭질 문제
    Algorithm : BFS 알고리즘
    Date : 2022-03-12
*/

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

public class A_1697 {
    private static int N,K;
    private static Queue<Integer> queue = new LinkedList<>();
    private static int[] counter;
    private static int[] NEW_N = {-1,1,2};
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        K = in.nextInt();
        counter = new int[100001];

        counter[N] = 1;
        queue.add(N);
        System.out.println(bfs());

    }

    public static int bfs(){
        while(!queue.isEmpty()){
            int temp = queue.poll();

            if(temp == K) return counter[temp]-1;

            for(int i=0; i<3; i++){
                int new_n;
                if(i==2) new_n = temp * NEW_N[i];
                else new_n = temp + NEW_N[i];             
                
                if(new_n >= 0 && new_n<100000 && counter[new_n]==0){
                    queue.add(new_n);
                    counter[new_n] = counter[temp]+1;
                }
            }
            
        }
        return -1;
    }
}