[백준]12851_숨바꼭질 2

[문제 링크] boj 12851 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

[생각 흐름]

이전에 숨바꼭질 문제 3번과 동일한 문제 유형이었다. 추가적인 문제 조건으로 몇 가지의 방법으로 최단시간에 도착할 수 있는지가 포인트였다.

 

먼저 동생보다 수빈이가 앞에 있다면 n-m을 리턴해준다, 만약 같은 자리에 있어도 바로 리턴해준다

여기서 가는 방법의 수는 한 가지이므로 한가지 이고, 이를 생각하지 않으면 78%에서 에러가 난다 

 

또한 메모리 초과나 시간 초과가 나지 않기 위해서는 visit을 이용한다. 

이전에는 큐에 넣음과 동시에 visit을 변경했지만 이번에는 여러 가지 방법의 수를 알아야 하므로 queue에서 나온 후에 방문처리를 해준다

(큐에 있는 상태는 시간 순으로 정렬된 상태 이므로)

그리고 만약 큐에서 꺼낸 상태가 동생의 상태와 동일하면 cnt를 증가시켜주고, 갈 수 있는 최단시간을 저장해준다

 

이후에 갈 수 있는 최단시간보다 긴 시간을 사용 하는 큐의 값이 나오면 진행하지 않고 리턴해주는 방식으로 구현하였다.

 

[코드]

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

public class Main {
    private static int atime = Integer.MAX_VALUE;
    private static int acnt = 0;

    private static void bfs(int n, int m) {
        if (m <= n) {
            atime = (m < n) ? n - m : 0;
            acnt = 1;
            return;
        }

        boolean visit[] = new boolean[100001];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n, 0});
        visit[n] = true;

        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            //System.out.println("Arrays.toString(tmp) = " + Arrays.toString(tmp));
            int time = tmp[1] + 1;
            int now = tmp[0];
            visit[now] = true;

            if (now == m && atime == Integer.MAX_VALUE) {
                atime = time - 1;
                acnt++;
                continue;
            }
            if (now == m && atime == time - 1) {
                acnt++;
                continue;
            }

            if (atime < time) continue;
            if (now * 2 < 100001 && !visit[now * 2]) q.add(new int[]{now * 2, time});
            if (now + 1 < 100001 && !visit[now + 1]) q.add(new int[]{now + 1, time});
            if (0 <= now - 1 && !visit[now - 1]) q.add(new int[]{now - 1, time});

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        bfs(n, m);
        System.out.println(atime + "\n" + acnt);
    }
}