jiho_bae
Go devlog
jiho_bae
전체 방문자
오늘
어제
  • 분류 전체보기 (158)
    • JavaScript (38)
      • theory (34)
      • vanilla (4)
    • HTML & CSS (2)
    • Browser (3)
    • CS (6)
      • linux (1)
      • shell (2)
      • compiler (2)
    • DS & Algorithm (87)
      • theory (5)
      • basic (7)
      • programmers (30)
      • baekjoon (45)
    • Design Pattern (2)
    • Error (4)
    • Git & Github (4)
    • Tools (1)
    • 부트캠프 (4)
    • Small Tips (2)
    • Java (3)
    • test (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 1753 최단경로 javascript
  • 리코쳇 로봇 javascript
  • 자바스크립트 커링
  • 자바스크립트 이벤트 위임
  • 자바스크립트 sort는 왜 그모양일까
  • 퀵정렬 자바스크립트
  • 대충만든자판 javascript
  • 깃 이전 커밋에서 새 브랜치 만들기
  • 리액트 프로젝트 디버깅하기
  • safari invalid date error
  • javascript use strict
  • 자바스크립트 모듈 시스템
  • 가사 검색 자바스크립트
  • 덧칠하기 javascript
  • 13460 javascript nodejs
  • 25632 소수 부르기 게임
  • 백준 17406 nodeJS
  • 백준 자바스크립트 입력 템플릿
  • 자바스크립트 채팅방 스크롤
  • 프로그래머스 숫자카드나누기 javascript
  • fetch 취소하기
  • 억억단을 외우자 javascript
  • 카카오 코딩테스트 양궁대회 nodeJS
  • 계수정렬 자바스크립트
  • safari Date format NaN
  • JavaScript
  • 자바스크립트 배열의 특수함
  • 병합정렬 자바스크립트
  • 외벽 점검 javascript
  • 자바스크립트 비동기 마이크로 태스크 큐와 렌더링 과정

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jiho_bae

Go devlog

[백준] 13913 숨바꼭질4 - JavaScript(NodeJS)
DS & Algorithm/baekjoon

[백준] 13913 숨바꼭질4 - JavaScript(NodeJS)

2021. 5. 31. 11:08

문제

 

13913번: 숨바꼭질 4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

풀이



 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

1697번 문제의 연장선이다.

 

수빈이가 동생에게 도달하기까지의 최소 시간과 지나온 경로까지 구하면 된다.

방법은 BFS를 이용할 것인데, 지나온 경로를 추적하기 위해서 배열을 따로 선언한다.

 

주의할 점

문제에서 구할 것은 최단시간이므로
2에서 10까지 이동한다 할 때 2-4-5-10이 최단 시간 경로이며, 2-4-8-9-10, 2-3-4-5-10 등의 경우의 수를 제거해야 한다.

 

그러므로 위치 X에는 단 한 번 만의 방문이 가능하다.
방문여부를 확인하면서, 경로 배열에 다음 위치 X의 인덱스에 이전의 위치 값을 넣어준다.

 

그림으로 표현하면 다음과 같다.

 

 

BFS가 끝나면 위와 같이 도착 위치의 인덱스를 기준으로 역추적하면 된다.
이 때 인덱스를 역추적하면서 배열에 push 했다면, 마지막에는 reverse 메서드로 뒤집어주면 된다.

 

추가로
방문할 위치 X는 0<=X<=100,000를 만족해야 하며
같은 레벨의 트리(도달하기까지 동일한 시간이 소요되는 위치)를 지날 때는 소요된 시간이 동일하도록 코드로서 표현해야 한다.

 

코드는 다음과 같다.

 

코드

const sol = (input) => {
  const [N, K] = input.split(" ").map(Number);
  const path = Array.from({ length: 100100 }, () => 0);
  const visit = Array.from({ length: 100100 }, () => 0);
  function bfs(N) {
    const queue = [];
    queue.push([N, 0]);
    visit[N] = 1;
    while (queue.length) {
      const [cur, time] = queue.shift();
      if (cur === K) return time;
      for (next of [cur - 1, cur + 1, cur * 2]) {
        if (!visit[next] && next >= 0 && next <= 100000) {
          path[next] = cur;
          visit[next] = 1;
          queue.push([next, time + 1]);
        }
      }
    }
  }

  const time = bfs(N);
  const order = [];
  order.push(K);
  let prev = path[K];
  for (let i = 0; i < time; i++) {
    order.push(prev);
    prev = path[prev];
  }
  const result = `${time}\n${order.reverse().join(" ")}`;
  return result;
};

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    console.log(sol(line));
  })
  .on("close", () => {
    process.exit();
  });
저작자표시 (새창열림)

'DS & Algorithm > baekjoon' 카테고리의 다른 글

[백준] 14226 이모티콘 - JavaScript(NodeJS)  (0) 2021.06.01
[백준] 13549 숨바꼭질3 - JavaScript(NodeJS)  (0) 2021.06.01
[백준]1697번 숨바꼭질 - JavaScript(NodeJS)  (0) 2021.05.31
[백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS)  (0) 2021.05.29
[백준] 16929번 Two Dots - JavaScript(NodeJS)  (0) 2021.05.29
    'DS & Algorithm/baekjoon' 카테고리의 다른 글
    • [백준] 14226 이모티콘 - JavaScript(NodeJS)
    • [백준] 13549 숨바꼭질3 - JavaScript(NodeJS)
    • [백준]1697번 숨바꼭질 - JavaScript(NodeJS)
    • [백준] 16947번 서울 지하철 2호선 - JavaScript(NodeJS)
    jiho_bae
    jiho_bae
    하루에 한 걸음씩

    티스토리툴바