[백준] 1697 숨바꼭질(BFS)

접근 방법

• dx 배열에 이동 경로를 입력 int[] dx =  new int[]{-1, 1, 2}
• BFS 문제와 동일하게 Queue에 값을 넣어서 계속해서 알까기 진행 
• People class를 운영하여 걸린 시간을 계속해서 더해주었다. 
  -> People class 선언 시, static으로 하지 않으면 에러가 나서 static으로 선언해 주었다. 

 

특이점

• 기존에 BFS 문제들과 비교했을 때에 좌표가 아닌점이 신선했다.
• visited를 운영하지 않았더니 시간초과가 발생했다.
• visited 배열의 크기를 x,y 중에 큰 값으로 했더니, 10 19와 같이 x2후에 -1을 하는 케이스에서 오류가 발생해서
  입력 범위의 전체로 늘려주었다. 
  visited = new boolean[1000001];
• 원래 continue를 통해서 범위가 아닐 때 넘겨주었는데, max 값을 넘어갈 수 있다보니 
  continue가 아닌, queue에 들어갈 수 있는 조건을 추가해서 if문을 구성해주었다.
  if(nextX >= 0 && nextX < visited.length && !visited[nextX]) {

소스

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOK_1697 {
    static int[] map;
    static boolean[] visited;
    static class People{
        int x;
        int time;

        public People(int x, int time) {
            this.x = x;
            this.time = time;
        }
    }
    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        visited = new boolean[100001];
        System.out.println(bfs(x,y));
    }

    public static int bfs(int x, int y){
        People p = new People(x, 1);
        Queue<People> q = new LinkedList<>();
        q.add(p);

        int[] dx = new int[]{-1, 1, 2};
        boolean rNum = false;
        if(x == y) return 0;
        if(x > y) rNum = true;
        if(rNum) return x-y;

        while(!q.isEmpty()){
            People move = q.poll();

            for(int i=0; i<3; i++){
                int nextX;
                int time = move.time;
                if(i == 2){
                    nextX = move.x * dx[i];
                }else{
                    nextX = move.x + dx[i];
                }

                // 만약 만나면
                if(nextX == y) return time;
                if(nextX >= 0 && nextX < visited.length && !visited[nextX]) {
                    q.add(new People(nextX, time + 1));
                    visited[nextX] = true;
                }
            }
        }

        return -1;
    }
    public static void main(String[] args) throws IOException {
        solution();
    }
}