BFS - 백준(12851) 숨바꼭질2 - BFS 조건 추가

숨바꼭질 2 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

56478

15827

11019

25.625%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

4
2

 

---

풀이 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n,k;
    static Pos[] pos;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        if(n == k){
            System.out.println(0);
            System.out.println(1);
            return;
        }
        pos = new Pos[100001];


        for (int i=0; i<=100000;i++){
            pos[i] = new Pos(i,0,0);
        }

        Queue<Pos> q = new LinkedList<>();
        Pos start = pos[n];
        //방법 1 올리기
        start.cnt=1;
        q.offer(start);

        while (!q.isEmpty()){
            Pos now = q.poll();
            int nowp = now.p;
            int[] dir = {nowp-1,nowp+1,nowp*2};

            for(int i=0; i<3;i++){
                int newp = dir[i];
                if(newp <0 || newp>100000)continue;
                //두가지 처리해야함 첫 방문 그 다음 방문
                //1. 첫 방문  time이 여기서 check역할
                // 첫 방문시에는 모두 cnt가 1
                if(pos[newp].time == 0){
                    pos[newp].time = now.time+1;
                    pos[newp].cnt = now.cnt;
                    q.offer(pos[newp]);
                //두번째 이상 방문 일단 time이 0이 아닌 경우!
                    //두번째 이상 방문일때는 q에 넣지 않으나,
                    // 다음 newp에 time이 지금 time+1과 같아야함
                }else if(pos[newp].time == now.time+1){
                    //새로운 최단 방문이다! 방문 횟수 추가
                    pos[newp].cnt ++;
                }
            }
        }

        System.out.println(pos[k].time);
        System.out.println(pos[k].cnt);

    }

    static class Pos{
        int p;
        int time;
        int cnt;
        public Pos(int p,int time,int cnt ){
            this.p = p;
            this.time = time;
            this.cnt = cnt;
        }
    }
}

 

---

 

1. 최단 거리는 기존의 BFS로 찾는다. 

 

2. 최단 거리 외에 방법의 수

• 첫 노드는 첫 방법이니 방법을 1로 둔다.
• 다음 노드 방문부터는 기존 방법의 수를 넣는다.

 if(pos[newp].time == 0){
 pos[newp].time = now.time+1;
 pos[newp].cnt = now.cnt;
 q.offer(pos[newp]);
}

// 1에서 3으로 가는 방법을 임의로 가정해보자 (문제 정의랑 다름)
// 1-2-3  첫 방문임 모두 방법의 수는 1
// 1-4-3  두번째 방문 1은 방법의 수가 2번째이고, 4는 첫 방문이지만, 방법의 수를 2로 둬야함 
// 따라서 그냥 +1씩 올리는 것이 아니라, 이전 방법의 수를 대입해줘야한다. 
// 방법의 수를 노드끼리 맞춰주자

• 최단거리로 갈 수 있는 방법이지만, 기존에 방문한 적이 있는 노드 
  •  

else if(pos[newp].time == now.time+1){
 //새로운 최단 방문이다! 방문 횟수 추가
pos[newp].cnt = now.cnt+1;
}

//그냥 +1이 아니라, 이전 방법의 수에 +1해줘야한다.
// 해당 노드의 방문 수를 count하는게 목적이 아니라, 
// 최단 거리로 이동하는 방법의 수를 구하는 것이 목적 

// 1 에서 2로 가는 방법이 1+1과 1*2와 3-1의 3가지 방법이 있다고 해보자
// 첫번째 1+1로 방