숨바꼭질 3

📍 문제 설명

💡 접근

1초 후에 2*X의 위치로 가는게 아닌 0초 후에 2*X의 위치로 가는 조건으로 변경되었다.

방문했더라도 기록되어있는 방문 시각보다 현재 방문하려는 방문 시각이 더 작을 때는 값을 변경시켜주면 된다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n, m, v, e, k, answer, cnt, second;
    static int[] arr, dis = {-1, 1, 2};
    static long[] dp;
    static int[][] board;
    static int[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Integer> q;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        k = kb.nextInt();
        visited = new int[100001];

        System.out.println(T.solution());
    }


    private int solution() {
        q = new LinkedList<>();
        q.offer(n);
        visited[n] = 1;

        while(!q.isEmpty()) {
            int len = q.size();
            for(int i = 0; i < len; i++) {
                int cx = q.poll();
                if (cx == k) {
                    return visited[cx]-1;
                }
                for (int j = 0; j < dis.length; j++) {
                    int nx = 0;
                    if(j != 2) nx = cx + dis[j];
                    else nx = cx * dis[j];
                    if (nx < 0 || nx > 100000) continue;

                    //방문하지 않은 곳만 방문
                    //방문했더라도 현재 방문 시간이 더 작으면 넣어줘★
                    if(j != 2 && (visited[nx] == 0 || visited[nx] > visited[cx]+1)) {
                        visited[nx] = visited[cx] + 1;
                        q.offer(nx);
                    }
                    else if(j == 2 && (visited[nx] == 0 || visited[nx] > visited[cx])) {
                        visited[nx] = visited[cx];
                        q.offer(nx);
                    }
                }
            }
        }
        return 0;
    }

    private static class Point {
        private int x;
        private int second;

        public Point(int x, int second) {
            this.x = x;
            this.second = second;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", second=" + second +
                    '}';
        }
    }
}