백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 1987 알파벳 [DFS]

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 1987 알파벳 [DFS]

 

 

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

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

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

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

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

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

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

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


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

 

 

 

문제 출처 🏠

 

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

1987번: 알파벳

 

 

 

문제풀이 소감 🧑‍💻

전형적인 DFS 문제라고 생각해요.

거기다가 플러스로 가장 길게 움직이는 값을 찾아야 하니까 MAX 변수를 사용해서 가장 재귀가 깊게 탐색되는 경우를 찾는 것이 핵심인 문제입니다.

 

 

요구사항 📋

말이 지날 수 있는 최대의 움직임을 출력하여라.

1칸당 1개씩 증가하고, 한 번 지난 알파벳은 또 다시 지나갈 수 없다.

 

 

주의 ❗

BFS 로 탐색하게 되면, 최장 움직임을 찾을 수 없습니다.

어디를 먼저 탐색하느냐에 따라 다른 길로 가면 더 움직일 수 있는데도 더 움직이지 못한다고 판단하기 때문.

 

 

해결 전략 📝

 

DFS 로 재귀 탐색을하면서 찾는다.

재귀 호출 한번당 한 칸을 움직인 것으로 판단하여 move 파라미터의 값을 1씩 증가시켜 호출하고, 최댓값인지를 계속 확인해주면서 모든 탐색 경우의 수들 중 가장 깊게 재귀가 호출 된 경우를 찾는다.

 

이후, 가장 큰 값이 담겨있는 MAX 변수를 return

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_R, input_C] = input[0].split(" ").map(Number);
input.shift();
const [...input_board] = input;

function solution(R, C, board) {
  const start = (x, y, move) => {
    isPass[board[x][y]] = true;
    if (move > MAX) MAX = move;
    for (let i = 0; i < 4; i++) {
      const [mx, my] = [x + dr_x[i], y + dr_y[i]];
      if (mx < 0 || mx >= R || my < 0 || my >= C) continue;
      if (isPass[board[mx][my]]) continue;
      else {
        isPass[board[mx][my]] = true;
        start(mx, my, move + 1);
        isPass[board[mx][my]] = false;
      }
    }
  };

  const dr_x = [-1, 0, 1, 0];
  const dr_y = [0, 1, 0, -1];
  const isPass = {};
  let MAX = 0;

  board = board.map((v) => v.trim().split(""));

  start(0, 0, 1);

  return MAX;
}

console.log(solution(input_R, input_C, input_board));