18290 NM과 K (1)

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

•

1 ≤ N, M ≤ 10

•

1 ≤ K ≤ min(4, N×M)

•

격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

•

항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

예제 입력 4

Plain Text
복사

예제 출력 4

Plain Text
복사

My solution

N X M 격자

각 칸에는 정수

K 개의 칸 선택해 총합의 최댓값을 구하려 한다.

→ 재귀 호출을 하면서 sum은 매개변수를 통해 누적하고, 배열이 필요하지 않다.

재귀호출의 depth를 호출할 때마다 늘려주는 방식으로 K개의 숫자를 선택했는지 확인한다.

const DFS = (sum, depth) => {
    if (depth === K) {
      result = Math.max(sum, result);
      return;
    }
		...
		DFS(sum + grid[i][j], depth + 1);
JavaScript
복사

그리고 선택한 두 칸은 인접하면 안된다.

r행 c열의 칸이 (r, c)면 (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다

→ 선택한 칸에서 상하좌우로 한칸씩 이동하면서 이미 방문한 적 있는지 확인하고 방문한 곳이 인접해있는지 검사한다.

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
const isAdjacent = (x, y) => {
  for (let i = 0; i < 4; i++) {
    const nx = x + dx[i];
    const ny = y + dy[i];
    if (nx >= 0 && nx < N && ny >= 0 && ny < M && visited[nx][ny]) {
      return false;
    }
  }
  return true;
};
JavaScript
복사

매번 재귀호출마다 브루트포스로 이차원 배열을 탐색할 때 visited 배열과 함께 인접 여부를 검사해서 해당 칸이 유효한지 걸러낸다.

const DFS = (sum, depth) => {
  if (depth === K) {
    result = Math.max(sum, result);
    return;
  }
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (!visited[i][j] && isAdjacent(i, j)) {
        visited[i][j] = true;
        DFS(sum + grid[i][j], depth + 1);
        visited[i][j] = false;
      }
    }
  }
};
JavaScript
복사

Code

const solution = function (i) {
  const [[N, M, K], ...grid] = i
    .toString()
    .trim()
    .split('\n')
    .map(input => input.split(' ').map(Number));

  const visited = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => false)
  );
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  const isAdjacent = (x, y) => {
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && nx < N && ny >= 0 && ny < M && visited[nx][ny]) {
        return false;
      }
    }
    return true;
  };

  let result = Number.MIN_SAFE_INTEGER;
  const DFS = (sum, depth) => {
    if (depth === K) {
      result = Math.max(sum, result);
      return;
    }
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (!visited[i][j] && isAdjacent(i, j)) {
          visited[i][j] = true;
          DFS(sum + grid[i][j], depth + 1);
          visited[i][j] = false;
        }
      }
    }
  };

  DFS(0, 0);
  // BOJ 제출
  console.log(result);
  return result;
};

test('TC1', () => {
  expect(
    solution(`1 1 1
1`)
  ).toStrictEqual(1);
});
test('TC2', () => {
  expect(
    solution(`2 2 2
1 2
3 4`)
  ).toStrictEqual(5);
});
test('TC3', () => {
  expect(
    solution(`2 2 2
5 4
4 5`)
  ).toStrictEqual(10);
});
test('TC4', () => {
  expect(
    solution(`5 5 3
1 9 8 -2 0
-1 9 8 -3 0
-5 1 9 -1 0
0 0 0 9 8
9 9 9 0 0`)
  ).toStrictEqual(27);
});
JavaScript
복사