[백준] 도로의 개수 1577 JS

 

문제 해결 방식

우선 N,M의 범위가 100이하여서 n^2으로 풀었습니다.

DP문제라고 판단하여 테이블로 값을 갱신하면서 풀었습니다

(0,0)에서 시작해서 (N,M)까지 가는 최단거리이기 때문에

우상단을 향해 가는 값들만 고려했습니다.

DP[i][j] = DP[i][j-1] + DP[i-1][j];

그중에서 공사 중인 길은 제외하고 값을 더해나갔습니다.

 

로직 상에는 문제가 없는 것 같았는데 제출을 하자마자 다 틀리더라구요

알고보니 경로를 set에 저장할 때 키값의 문제였습니다

처음에는 ${a}${b}${c}${d} 이런 식으로 키값을 줬었는데

구분자 없이 키값을 주니 a,b,c,d값이 다름에도 같은 값으로 인식되어서 틀린 것 같아요

 

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const [size, k, ...k_List] = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n');

const [N, M] = size.split(' ').map(Number);
function solution(N, M, K_List) {
  const DP = Array.from(new Array(N + 1), () => new Array(M + 1).fill(0n));
  DP[0][0] = 1n;

  const dr = [0, 1];
  const dc = [1, 0];

  const construction = new Set();
  K_List.forEach(([a, b, c, d]) => {
    if (a < c || b < d) construction.add(`${a},${b},${c},${d}`);
    else construction.add(`${c},${d},${a},${b}`);
  });

  for (let i = 0; i <= N; i++) {
    for (let j = 0; j <= M; j++) {
      for (let k = 0; k < 2; k++) {
        const prevR = i - dr[k];
        const prevC = j - dc[k];
        if (prevR >= 0 && prevC >= 0) {
          if (!construction.has(`${prevR},${prevC},${i},${j}`)) {
            DP[i][j] += DP[prevR][prevC];
          }
        }
      }
    }
  }

  return DP[N][M].toString();
}

const answer = solution(
  N,
  M,
  k_List.map((k) => k.split(' ').map(Number)),
);

console.log(answer);