백준 1697 숨바꼭질 //BFS 큐

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

1697번: 숨바꼭질

 

BFS 작동원리 예시

 

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


public class Main_1697_유동훈 {
    static int N;	//현재위치
    static int K;	//목적위치
    static int[] check = new int[100001];	//index의 숫자올때까지 이동횟수(시간) 저장, 0이아님->방문O

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();

        if (N == K) {
            System.out.println(0);
        } else {
            bfs(N);
        }
    }

    /*
     * DFS : 재귀로 구현
     * BFS : 큐로 구현
     * 
     * 
     * 
     * 
     */
    static void bfs(int num) {
        Queue<Integer> q = new LinkedList<>();
        q.add(num);	//초기위치 큐에넣기
        check[num] = 1;	//초기위치 방문처리

        /*
         * 1. 큐에서 하나씩 뻄 => 기준
         * 2. 앞,뒤,점프 (범위안,노방문이면)경우의수 큐에추가  == 연결노드 큐에추가
         * 3. 목적지에 도착했으면 리턴
         * 4. 체크배열=기준값+1 => 시간경과 기록
         * 5. 큐가빌때까지 1,2,3,4 반복
         * 
         * 
         */
        while (!q.isEmpty()) 
        {
            int temp = q.poll();	//큐에서 방문할 위치

            for (int i = 0; i < 3; i++) 
            {
                int next;	//다음에 갈 위치

                if (i == 0) //앞
                {
                    next = temp + 1;
                } 
                else if (i == 1) //뒤
                {
                    next = temp - 1;
                } 
                else //점프
                {
                    next = temp * 2;
                }

                if (next == K) //목적지에 도달했으면 리턴
                {
                    System.out.println(check[temp]);
                    return;
                }

                //다음갈위치가 범위안 && 방문안함->큐에 추가
                if (next >= 0 && next < check.length && check[next] == 0) 
                {
                    q.add(next);
                    check[next] = check[temp] + 1;
                }
            }
        }
    }
}

 

DFS구현 <= 재귀

BFS구현 <= 큐