[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");
Author And Source
이 문제에 관하여([BOJ] 5014 스타트링크 | BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mingsomm/BOJ-5014-스타트링크저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)