백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 5014 스타트링크

백준/ Silver 1 문제 , 백준 Node.js 자바스크립트 5014 스타트링크

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

https://www.acmicpc.net/problem/5014

5014번: 스타트링크

 

 

 

문제풀이 소감 🧑‍💻

 

기본적인 BFS 문제이다.

 

이런 비슷한 문제가 숨바꼭질 문제가 있다.그 문제를풀어봤다면 비슷한 유형의 문제라 쉽게 풀 수 있을 것이다.

 

요구사항 📋

 

F : 건물 최대 높이

S : 시작 위치

G : 도착 위치

U : 올라가는 버튼을 눌러서 이동할 수 있는 거리

D : 내려가는 버튼을 눌러서 이동할 수 있는 거리

 

 

S층에서 G층으로 갈 수 있는 최소한의 버튼 클릭 수를 출력하자.

만약, 아무리 해도 갈 수 없다면 'use the stairs' 를 출력한다.

 

 

주의 ❗

S와 G가 처음부터 같을 수 도 있다. 그럴때는 0 출력.

 

해결 전략 📝

최소거리를 찾는 문제이므로 BFS를 활용한다.

 

또한 한 번 방문한 위치를 또 방문할 수 있을수도 있기때문에 배열을 따로 선언하여 최솟값만 담아주도록하면서 방문처리도 동시에 같이 해준다.

 

최솟값을 담아야하므로 당연히 초깃값은 Infinity로 다 설정한다.

 

이동 위치는 이동할 위치까지 움직일 횟수가 이동할 위치에 담긴 값보다 작을 경우에만 이동한다.

 

목표층인 G층에 다다르면 움직일 거리를 바로 return 시킨다.

 

 

 

정답 💯

 

const input = require("fs").readFileSync("/dev/stdin").toString().trim();
const [...info] = input.split(" ").map(Number);

function solution(F, S, G, U, D) {
  const bfs = (s) => {
    let dq = [[s, 0]];
    while (dq.length !== 0) {
      const [now, cnt] = dq[0];
      dq.shift();
      for (let i = 0; i < 2; i++) {
        const move = now + dr[i];
        if (move < 1 || move > F) continue;
        if (move === G) return cnt + 1;
        if (cnt + 1 < floor[move]) {
          floor[move] = cnt + 1;
          dq.push([move, cnt + 1]);
        }
      }
    }
    return "use the stairs";
  };
  const floor = Array.from({ length: F + 1 }).fill(Infinity);
  const dr = [U, -D];
  if (S === G) return 0;

  return bfs(S);
}

console.log(solution(...info));