오늘 풀어본 문제는
백준 12851번 숨바꼭질 2 입니다.

📕 문제 링크

❗️코드

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

class Subin
{
    int x,cnt;

    public Subin(int x, int cnt)
    {
        this.x = x;
        this.cnt = cnt;
    }
}
public class Main {
    static int [] map;
    static int [] move = {-1,1,2};
    static int [] isVis;
    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 k = Integer.parseInt(st.nextToken());

        if(n > k)
        {
            System.out.printf("%d\n%d",n-k,1);
            return;
        }
        map = new int[100001];
        isVis = new int[100001];
        Arrays.fill(isVis,Integer.MAX_VALUE);

        Queue<Subin> q = new LinkedList<>();
        q.add(new Subin(n,0));

        int minCnt = Integer.MAX_VALUE;
        int cnt = 0;
        while(!q.isEmpty())
        {
            Subin cur = q.poll();
            if(isVis[cur.x] > cur.cnt) isVis[cur.x] = cur.cnt;
            if(cur.cnt > minCnt) break;

            if(cur.x == k)
            {
                minCnt = cur.cnt;
                cnt++;
            }

            for(int i = 0; i < 3; ++i)
            {
                int m;
                if(i == 2) m = cur.x * move[i];
                else m = cur.x + move[i];

                if(!isValid(m) || cur.cnt >= isVis[m]) continue;
                q.add(new Subin(m,cur.cnt+1));
            }
        }


        System.out.printf("%d\n%d",minCnt,cnt);
    }
    static boolean isValid(int x)
    {
        return x >= 0 && x < 100001;
    }
}

📝 풀이

bfs문제입니다.
큐는 fifo구조이기 때문에, 시간 순서대로 숨바꼭질을 진행시킬 수 있습니다.
이를 활용하여 이동하다가 처음 동생을 마주친 순간을 최소값으로 정의해줍니다.
방문배열 isVis를 정수배열로 정의하여, 해당 위치에 도달했던 시점중 최소 시간값을 저장해두고, 그 시간보다 크다면 반복에서 제외해주는 방식을 사용했습니다.
예를들어 3이라는 위치에 처음 도달한 시간이 1초일때, 3에서 이동할 수 있는 위치는 이전과 동일하게 2,4,6이며 1초가 넘어가는 2초,3초 시점에서 3으로 넘어와봤자 이전보다 먼저 동생에게 도달할 경우의 수는 존재하지 않습니다.
위의 방식으로 조건에 부합하는 데이터만 큐에 담아주면 최솟값과 중복카운트를 얻어낼 수 있습니다.

📜 후기

이전에 풀었던 bfs문제들과 다르게 경우에 따라 중복을 허용해주어야하는 문제여서, 방문배열을 효율적으로 활용하는게 조금 헷갈렸던것 같아요 ㅠ
요즘 문제를 너무 편식하는것 같아서 친구가 골라준 문제랍니다 ㅋㅋㅋㅋㅋ
의외로 잘골라줘서 재밌게 풀었어요 ~.~