숨바꼭질2

📍 문제 설명

💡 접근

가장 빠른 시간이 몇 초 후 인지, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지

한가지만 구하는게 아니라 두가지 동시에 구해야되는 문제여서 조금 생각을 했다. 

중복인 지점을 걸러내야하지만 동일한 시간에 방문한 지점이면 답이 될수도 있기때문에 해당 조건을 넣어야만 했다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, h, k, answer,cnt, max, min, L, R, C, second = Integer.MAX_VALUE;
    static int[][] board;
    static int[] dis = {-1,1,2};
    static int[] visited = new int[200];
    static int[] ch,pm, combi;
    static boolean flag = false;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt(); //수빈이 위치
        m = kb.nextInt(); //동생 위치
        if(n==m) {
            System.out.println(0);
            System.out.println(1);
        }else {
            T.solution(n);
            System.out.println(second);
            System.out.println(cnt);
        }
    }

    private void solution(int n) {
        Queue<Integer> q = new LinkedList<>();
        //수빈이 지점 넣어놓기
        q.offer(n);
        //경과 시간
        visited[n] = 1;

        while(!q.isEmpty()) {
            int len = q.size();//1 3 9
            System.out.println(q);
            System.out.println(Arrays.toString(visited));
            for(int i = 0; i < len; i++) {
                int cx = q.poll();
                //현재 방문하려는 시간이 동생을 찾은 시각보다 크면 볼 필요 없음
                if(second < visited[cx]) return;
                //3가지 방향으로 이동(x-1, x+1, 2*x)
                for(int j = 0; j < 3; j++) {
                    int nx = 0;
                    if(j != 2) nx = cx + dis[j];
                    else nx = cx * dis[j];

                    if(nx < 0 || nx > 100000) continue;

                    //다음 지점에서 동생 찾았다!
                    if(nx == m) {
                        cnt++;
                        //현재까지 걸린시각을 기록
                        second = visited[cx];
                    }

                    //다음의 경우의 수가 이미 방문한 곳이어도
                    //동일한 시간에 방문한 곳이라면 답이 될 수도 있으니 큐에 넣어준다!
                    if(visited[nx] == 0 || visited[nx] == visited[cx] + 1) {
                        q.offer(nx);
                        visited[nx] = visited[cx] + 1;
                    }
                }
            }
        }
    }


}