백준 16173 < 점프왕 쩰리 (Small) > JavaScript

📍문제 링크

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

16173번: 점프왕 쩰리 (Small)

 

📍알고리즘 분류

- 구현

- 그래프 이론

- 브루트포스

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색

 

📍문제 풀이

구현으로도 해결할 수 있는 문제이지만 DFS를 사용해서 풀자

- 크기가 작아서 구현으로 해결 가능

 

DFS를 사용하는 이유

- 빠르게 목표 지점에 도달하는 경로 하나만 찾으면 프로그램을 종료할 수 있어서

 

📍의사 코드

/*
1. 행렬 형태로 주어진 데이터를 2차원 배열로 가공
2. 2차원 배열의 (0,0) 에서 DFS 시작
  2.1. 방문 기록을 저장할 동일한 사이즈의 2차원 배열 생성
  2.2. 스택에 시작 지점의 인덱스를 미리 넣어 생성
  2.3. 스택에 있는 지점에서 하, 우 방향 진출 가능한지 탐색하고 유효하면 stack에 push
  2.4. 지점의 값이 음수이면 종료
  2.5. 반복문이 끝나면 종료
*/

 

📍코드 (JavaScript)

const [in1, ...in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const N = +in1;
const map = in2.map((row) => row.split(" ").map(Number));

const dfs = () => {
  const isVisited = Array.from({ length: N }, (column) =>
    Array.from({ length: N }, (row) => false),
  );
  const stack = [[0, 0]];
  while (stack.length) {
    const [y, x] = stack.pop();
    const val = map[y][x];
    if (val < 0) return "HaruHaru";

    if (y + val < N && !isVisited[y + val][x]) {
      stack.push([y + val, x]);
      isVisited[y + val][x] = true;
    }
    if (x + val < N && !isVisited[y][x + val]) {
      stack.push([y, x + val]);
      isVisited[y][x + val] = true;
    }
  }
  return "Hing";
};

console.log(dfs());