백준 숨바꼭질2 12851 java

문제링크

문제접근

• bfs 활용하여 최단시간 측정
• 목표인 K 만나도 끝내는게 아니라 해당 초 반복문 수행

코드

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

public class baek_12851 {
    static int N, K;
    static int[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        if(N == K){
            System.out.println(0);
            System.out.print(1);
            return;
        }
        visit = new int[100001];
        bfs();
    }
    private static void bfs(){
        Queue<Integer> que = new LinkedList<>();
        que.add(N);
        visit[N] = 1;
        int cntTime = 0;
        int cntWay;
        while(!que.isEmpty()){
            int size = que.size();
            boolean isFind = false;
            cntWay = 0;
            for(int s=0;s<size;s++){
                int now = que.poll();
                int walk1 = now + 1;
                if(walk1 >= 0 && walk1 <= 100000 && visit[walk1] <= 3){
                    que.add(walk1);
                    visit[walk1]++;
                    if(walk1 == K){
                        isFind = true;
                        cntWay++;
                        visit[walk1]--;
                    }
                }
                int walk2 = now - 1;
                if(walk2 >= 0 && walk2 <= 100000 && visit[walk2] <= 3){
                    que.add(walk2);
                    visit[walk2]++;
                    if(walk2 == K){
                        isFind = true;
                        cntWay++;
                        visit[walk2]--;
                    }
                }
                int jump = now * 2;
                if(jump >= 0 && jump <= 100000 && visit[jump] <= 3){
                    que.add(jump);
                    visit[jump]++;
                    if(jump == K){
                        isFind = true;
                        cntWay++;
                        visit[jump]--;
                    }
                }
            }
            cntTime++;
            if(isFind){
                System.out.println(cntTime);
                System.out.print(cntWay);
                break;
            }
        }
    }
}

결과

정리

1. K 만났을 때 방문처리 해제해줘야 함
2. 경로의 수가 아닌 방법의 수를 찾는것이다.

• ex) N=1, K=3일 때 똑같이 경로는 1->2->3 이지만, (걷기,걷기),(순간이동,걷기)로 다르다.

3. N == K 일 때의 경우 체크