백준 12851 : 숨바꼭질2

💡기본 정보

유형
: DFS/BFS
풀이 날짜
: 2025년 01월 25일 
풀이방법 한줄 요약
: BFS를 활용해서 방문 체크하며 여러 최단 경로 찾기

 

💡문제에서 구해야 할 것

수빈이는 동생과 숨바꼭질 중
수빈이는 현재 점 N에 있고 , 동생은 점 K에 있음 
N과 K 모두 0 이상 100000 임
수빈이는 걷거나 순간이동을 할 수 있음. 수빈이의 위치가 X일때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 됨

순간이동을 하는 경우엔 2*X의 위치로 이동하게 됨
수빈이와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고 가장 빠른 시간으로 찾는 방법이 몇가지 인지 구하는 프로그램
- 입력 : 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어짐. N과 K는 정수
- 출력 : 첫 번째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력
             두 번째 줄에 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력

💡알고리즘 설계

- 1697번과 동일한 방식으로 최단 경로를 찾는 것이므로 BFS를 활용해서 구현

https://sterncodingstory.tistory.com/entry/%EB%B0%B1%EC%A4%80-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88

백준 1697 : 숨바꼭질

- 이외에도 경로를 저장하는 배열을 활용해 개수 측정

💡CODE

const fs = require("fs");
const [N, K] = fs.readFileSync(0,"utf8").toString().trim().split(" ").map(Number);

function BFS(start, target) {
    const queue = [[start, 0]];
    const visit = new Array(100001).fill(Infinity);
    const answer = new Array(100001).fill(0);
    visit[start] = 0;
    answer[start] = 1;

    while (queue.length) {
        const [curr, time] = queue.shift();

        for (const next of [curr - 1, curr + 1, curr * 2]) {
            if (next >= 0 && next <= 100000) {
                if (visit[next] > time + 1) {
                    visit[next] = time + 1;
                    queue.push([next, time + 1]);
                    answer[next] = answer[curr];
                } else if (visit[next] === time + 1) {
                    answer[next] += answer[curr];
                }
            }
        }
    }
    return [visit[target], answer[target]];
}

const [minTime, ways] = BFS(N, K);
console.log(minTime);
console.log(ways);

 

💡시간복잡도

💡 틀린 이유 & 틀린 부분 수정

1697번에서는 visit배열을 true/false로 했는데 이 문제에서는 시간으로 관리해야했음

 

💡 다른 풀이 or 기억할정보

최단 경로의 경우의수 초기값을 1로 정해야하는 이유
 : 처음 최단 시간을 구할 때 생긴 경로를 경우의 수에 포함시켜야 함