[BOJ] 5014 스타트링크 | BFS

Problem | 스타트링크


✨ 접근 방식

변수 설명
F : 건물의 최고층
S : 내가 있는 현재 층
G : 가고자하는 층
U : 올라갈 수 있는 층
D : 내려갈 수 있는 층

  • 방문한 노드는 다시 방문하지 않는다

  • (현재있는 층+U), (현재있는 층-D)가 건물의 층 범위에 맞아야한다.

    두 가지 조건만 고려하면 되는 문제다.

  • 최종 답은 BFS의 level 이 답이다.

    만약, flag값의 변동이 없다면 찾지 못하고 while문을 종료한 것이기 때문에 "use the stairs"를 출력해준다.

- ✔️ 전체코드

const { log } = require("console");
const fs = require("fs");
const { isBuffer } = require("util");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [F,S,G,U,D]=input[0].split(' ').map(Number);

let visited=new Array(F+1).fill(false);
let time=0;
let flag=true;
function BFS(){
  let queue=[];
  queue.push(S);
  visited[S]=true;
  while(queue.length){
    let len=queue.length;
    for(let i=0;i<len;i++){
      let x=queue.shift();
      if(x===G){
        flag=false;
        break;
      }
      // up 누른 경우의 체크
      if((x+U) <= F && visited[x+U]===false){
        // 범위 안에 맞고, 방문하지 않은 노드일 때
        queue.push(x+U);
        visited[x+U]=true;
      }
      if((x-D)>=1 && visited[(x-D)]===false){
        queue.push(x-D);
        visited[x-D]=true;
      }
    }
    if(!flag) break;
    time++;
  }
}

BFS();
if(!flag) console.log(time);
else console.log("use the stairs");

좋은 웹페이지 즐겨찾기