백준 1697 숨바꼭질 - JAVA

1697 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int N,K;
    static boolean[] visit;
    static int[] move = {1, -1, 2};
    static int MAX = 100001;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        visit = new boolean[MAX];
        
        bw.write(String.valueOf(bfs()));
        bw.flush();
    }
    
    private static int bfs() {
        visit[N] = true;
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            
            for (int i = 0; i < size; i++) {
                int current = queue.poll();
                
                if (current == K) {
                    return count;
                }
                for (int j = 0; j < 3; j++) {
                    int nN = (j == 2) ? current * move[j] : current + move[j];
                    if (nN >= 0 && nN < MAX && !visit[nN]) {
                        visit[nN] = true;
                        queue.offer(nN);
                    }
                }
            } 
            count++;
        }
        return -1;
    }
}

 

 

알고리즘 설명

---

BFS 알고리즘의 기본은 큐의 형태를 띄고 있습니다. 1초를 간격으로 poll()된 맨 앞의 원소가 갈 수 있는 세 가지의 경우를 레벨화 해놓고 생각하면 쉽게 풀 수 있습니다. 초를 count로 설정하고, 반복문이 어떻게 들어가는지 그림으로 보시겠습니다.

그림처럼 해당 숫자의 -1, +1, x2 각 세가지의 조건으로 중복되지 않는 숫자가 큐에 들어옵니다. 예를 들면 count=1 에서는 [4,6,10]
count=2에서는 [3,8,7,12,9,11,20]처럼 말이죠. 이렇게 count를 늘려가면서 처음 K를 찾는다면 해당 count가 K를 찾을 수 있는 최단 시간이라는 것을 알 수 있습니다. 어렵게 설명하기보다는 직관적으로 그래프를 그리는 것이 이해에 도움이 될것이라고 생각했습니다 :)

 

코드 해석

---

visit[] 배열을 사용해 방문 여부를 체크하고, N에서 시작해 큐에 넣습니다. 큐에서 하나씩 꺼내어 +1, -1, *2를 시도하며, K에 도달하면 바로 탐색을 종료하고 그때까지의 횟수를 출력합니다. 각 레벨마다 큐의 크기만큼 반복문을 돌며 가능한 모든 위치로 이동합니다. K에 도달하면 그때까지의 이동 횟수를 반환합니다.
 
삼항연산자에 주의하여 코드를 확인하시면 좋을것  같습니다. 이번 문제는 삼항연산자로 코드의 길이가 대폭 줄어들었습니다.