기사 배치하기

성공여부

걸린시간(분)

정리

완료

문제출처

제로베이스

생성 일시

Apr 17, 2025 02:12 PM

1️⃣ 문제

2️⃣ 문제 해결 전략

그냥 평소 dfs 백트래킹 문제 처럼 풀면 됨

방문좌표(배열)를 set으로 관리하려면, JSON.stringify로 좌표를 변환하여 push하고 새로운 좌표도 마찬가지로 JSON.stringify로 변환하여 has로 방문 여부를 확인한다!

3️⃣ 코드 및 설명

내 코드

dfs 까지는 다 구현했으나...

각 기사의 순서가 중요하다고 생각해서 마무리를 하지 못했음

하지만 dfs만으로도 모든 경우의 수를 구하기 때문에 굳이 순서를 따질 필요가 없음!

모범 코드


function solution(N, K, board) {
  var answer = 0;
  var knight = [];

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 0) {
        knight.push([i, j]);
      }
    }
  }

  var dx = [-1, -2, -2, -1, 1, 2, 2, 1];
  var dy = [-2, -1, 1, 2, 2, 1, -1, -2];
  var occupied = new Set([]);

  function dfs(idx, result, arr) {
    if (idx === K) {
      answer = Math.max(answer, result);
      return;
    }
    for (let k = idx; k < K; k++) {
      var [curx, cury] = knight.pop();
      for (let i = 0; i < 8; i++) {
        var [newx, newy] = [curx + dx[i], cury + dy[i]];
        const stringifiedXY = JSON.stringify([newx, newy]);
        const isOccupied = occupied.has(stringifiedXY);
        if (newx >= 0 && newx < N && newy >= 0 && newy < N && !isOccupied) {
          occupied.add(stringifiedXY);
          dfs(idx + 1, result + board[newx][newy], [...arr, [newx, newy]]);
          occupied.delete(stringifiedXY);
        }
      }
      knight.push([curx, cury]);
    }
  }

  dfs(0, 0, []);

  return answer;
}

console.log(
  solution(7, 3, [
    [2, 0, 6, 5, 7, 8, 4],
    [5, 7, 7, 8, 7, 4, 5],
    [8, 5, 9, 6, 5, 9, 6],
    [7, 9, 4, 5, 0, 8, 7],
    [9, 8, 5, 9, 7, 8, 8],
    [7, 0, 7, 4, 3, 7, 4],
    [7, 9, 9, 5, 8, 4, 3],
  ])
);

4️⃣ 시간복잡도

O(8**K)