숨바꼭질 2

📍 문제 설명

 

💡 접근

인프런 추천 문제에서 풀었던 문제인데 문제 순서대로 다시 풀어보기로 했다.

 

모든 경로에 대해서 방문 체크를 하지 않는다면 시간 초과 판정을 받을거다.

특정 지점에 대해서 방문 체크를 하지 않아야한다.

그 이전의 값에도 빠른 시간이 될 수 있기 때문에 바로 직점에 대해서만 체크하지 않는 것은 오류가 있다.

같은 시간에 방문했는데 똑같은 지점일 때는 그 중복된 지점들이 빠른 시간이 될수도 있으니 그대로 넣어주면 된다.

 

같은 시간에 방문한 곳인지 확인하기 위해서 boolean이 아닌 int로 걸린 시간을 넣어주었다.

 

 

👩‍💻 코드

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());
        cnt = 1;
        while(!q.isEmpty()) {
            if(q.poll() == k) cnt++;
        }
        System.out.println(cnt);
    }


    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(visited[nx] == 0 || visited[nx] == visited[cx] + 1) {
                        visited[nx] = visited[cx] + 1;
                        q.offer(nx);
                    }
                }
            }
            second++;
        }
        return 0;
    }

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

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

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