백준 2210 < 숫자판 점프 > JavaScript

📍문제 링크

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

2210번: 숫자판 점프

 

📍알고리즘 분류

- 그래프 이론

- 브루트포스

- 그래프 탐색

- 깊이 우선 탐색

 

📍문제 풀이

숫자가 담긴 5 x 5 이차원 배열이 주어진다. 2차원 배열에서 6개의 원소를 연결하여 만들 수 있는 수열의 가짓수를 출력한다

- 왔던 길을 되돌아갈 수 있다

 

☑️재귀 DFS를 사용

- 매개변수로 수열을 사용하여 길이가 6이 되기 전까지는 이차원 배열의 상하좌우를 탐색하여 수열에 더하고 재귀 호출

- 수열의 길이가 6이 되면 Set 객체에 더한다

(Set 객체는 중복을 허용하지 않기 때문에 그냥 더해도 됨)

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const output = new Set();

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const board = input.map((row) => row.split(" ").map(Number));

  const dfs = (y, x, text = "") => {
    const sequence = text + board[y][x];
    if (text.length === 6) {
      output.add(text);
      return;
    }
    // 상하좌우 탐색
    if (y - 1 >= 0) dfs(y - 1, x, sequence);
    if (y + 1 <= 4) dfs(y + 1, x, sequence);
    if (x - 1 >= 0) dfs(y, x - 1, sequence);
    if (x + 1 <= 4) dfs(y, x + 1, sequence);
  };

  for (let i = 0; i < 5; i++) {
    for (let j = 0; j < 5; j++) {
      dfs(i, j);
    }
  }
  console.log(output.size);
});