백준(BOJ) 1697 : 숨바꼭질 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

전형적인 BFS문제이다. 주의할 점은,

1. 좌표값이 0 일 때는 X-1, X*2를 해선 안된다.

2. 좌표값이 K(동생의 위치) 보다 클 때는 X+1, X*2를 할 필요가 없다.

 

코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        if(n >= k) {
            System.out.println(n - k);
        } else {
            boolean[] visited = new boolean[k * 2 + 1];
            visited[n] = true;
            Queue<Status> queue = new LinkedList<Status>();
            queue.offer(new Status(n, 0));
            
            int answer = 0;
            
            outer : while(!queue.isEmpty()) {
                Status poll = queue.poll();
                int position = poll.getPosition();
                int time = poll.getTime();
                    
                for(int i = 0; i < 3; i++) {
                    int nextPosition = getNextPosition(position, k, i);
                    
                    if(nextPosition != -1 && !visited[nextPosition]) {
                        
                        if(nextPosition == k) {
                            answer = time + 1;
                            break outer;
                        }
                        
                        visited[nextPosition] = true;
                        queue.offer(new Status(nextPosition, time + 1));
                    }
                }
            }
            
            System.out.println(answer);
        }
    }
    
    private static int getNextPosition(int position, int k, int idx) {
        int nextPosition = -1;
        
        switch (idx) {
        case 0:
            if(position > 0) {
                nextPosition = position - 1;
            }
            break;
        case 1:
            if(position > 0 && position < k) {
                nextPosition = position * 2;
            }
            break;
        default:
            if(position < k) {
                nextPosition = position + 1;
            }
            break;
        }
        
        return nextPosition;
    }
    
    private static class Status {
        private int position;
        private int time;
        
        public Status(int position, int time) {
            this.position = position;
            this.time = time;
        }
        
        public int getPosition() {
            return position;
        }
        public int getTime() {
            return time;
        }
    }
}