백준 1697 : 숨바꼭질

💡기본 정보

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

 

💡문제에서 구해야 할 것

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

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

💡알고리즘 설계

- 최단 경로를 찾는 것이므로 BFS를 활용해서 구현

💡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(false);
    visit[start]=true;

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

console.log(BFS(N,K));

 

💡시간복잡도

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

const visit = Array(100001).fill(false) 를 할때 100000로 크기를 설정해서 오류 발생 범위를 초과하지 않기 위해 100001로 설정해야함

💡 다른 풀이 or 기억할정보

-