[BOJ] 백준 12851 숨바꼭질 2

출처: www.acmicpc.net/problem/12851 

 Input 
5 17 

 Output 

4

2

※ 5 →  순간이동 → 10 →  걷기 → 9 →  순간이동 → 18 →  걷기 →17   ▶ 4초

※ 5 →  걷기 → 4 →  순간이동 → 8 →  순간이동 → 16 →  걷기 →17   ▶ 4초

 

[BOJ] 1697 숨바꼭질에서 구현했던 BFS 와는 다르게 특정 위치를 중복 방문해줘야 합니다.

[BOJ] 백준 1697 숨바꼭질

 Input 
1 4

 Output 

2

2

최단시간 2초가 걸리는 경로는 다음과 같습니다.

▶ 1 - (+1) - 2 - (*2) - 4

▶ 1 - (*2) - 2 - (*2) - 4

중간에 지점 『2』에 중복방문하여 동일한 최단 시간을 얻을 수 있습니다.

숨바꼭질 1에서 구현했던 코드에서는 최단시간만 구하면 되었기에 

특정 지점에 동일한 시간 다른 경로로 도달한 경우는 재방문이었기에 제외 되었습니다.

 

 Input 
3 10

 Output 

3

2

▶ 3 - (*2) - 6 - (-1) - 5 - (*2) - 10

▶ 3 - (+1) - 4 - (+1) - 5 - (*2) - 10

따라서 재방문 처리시, 특정 지점에 도달한 경로가 더 빠른 경로인지 확인하여 재방문을 허용합니다.

(+ 특정 지점을 동일한 시간 다른 경로로 방문한 경우도 재방문 허용)

 

 Input 
1000 0

 Output 

1000

1

---

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

class Subin {
    int elapsedTime;
    int position;
    // Getter, Setter 생략

    public Subin(int t, int p) {
        elapsedTime = t;
        position = p;
    }
    
}

public class Main {

    public static int result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());

        result = Math.abs(N - K);
        
        // 방문 여부 표시 0 <= N,K <= 100,000
        boolean[] visited = new boolean[100001];
        Queue<Subin> queue = new LinkedList<>();
        Queue<Subin> resultQueue = new LinkedList<>();
        queue.add(new Subin(0, N));
        
        while(!queue.isEmpty()) {
            
            Subin current = queue.poll();
            
            // K지점에 도착했다면
            if(current.position == K) {
                resultQueue.add(current);
                if(result > current.elapsedTime) {
                    result = current.elapsedTime;
                }
            }
            
            // pop한 뒤 방문 표시하는 것은 동일하다.
            visited[current.position] = true;

            // 방문여부에 따라 Queue에 넣을지 말지 결정한다.
            // 현재 지점에 대해서 -1,+1,*2
            if(current.position-1 >= 0 && !visited[current.position -1]) {
                queue.add(new Subin(current.elapsedTime + 1, current.position - 1));    
            }
            if(current.position+1 <= 100000 && !visited[current.position +1]) {
                queue.add(new Subin(current.elapsedTime + 1, current.position + 1));    
            }
            if(current.position*2 <= 100000 && !visited[current.position *2]) {
                queue.add(new Subin(current.elapsedTime + 1, current.position * 2));    
            }
        }
        
        System.out.println(result);

        int resultCnt = 0;
        Iterator<Subin> it = resultQueue.iterator();
        while(it.hasNext()) {
            Subin subin = it.next();    
            if(subin.elapsedTime == result) {
                resultCnt++;
            }
        }
        System.out.println(resultCnt);
    }
}