14500 테트로미노

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

•

정사각형은 서로 겹치면 안 된다.

•

도형은 모두 연결되어 있어야 한다.

•

정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

My solution

https://girawhale.tistory.com/35

브루트포스로 matrix의 모든 좌표를 하나씩 방문해서 visited로 방문 체크를 한 뒤 DFS를 진행한다.

5가지 모양에 대해서 DFS로 탐색해나가는 방식이다.

let result = Number.MIN_SAFE_INTEGER;
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  function DFS(y, x, depth, sum, visit) {
    if (depth >= 4) {
      result = Math.max(result, sum);
      return;
    }

    for (let k = 0; k < 4; k++) {
      const ny = y + dy[k];
      const nx = x + dx[k];

      if (!(ny < 0 || nx < 0 || ny >= N || nx >= M || visit[ny][nx])) {
        visit[ny][nx] = true;
        DFS(ny, nx, depth + 1, sum + matrix[ny][nx], visit);
        visit[ny][nx] = false;
      }
    }
  }
JavaScript
복사

DFS로 sum을 최댓값으로 업데이트하고 나서 테트로미노 중 T모양에 해당하는 4가지 케이스에 대한 에지케이스 처리를 한다. 이 모양들이 가진 총합을 계산하고 sum을 최댓값으로 업데이트하는 함수가 아래와 같다.

function checkEdgeCaseSum(y, x) {
    // ㅏ
    if (y + 2 < N && x + 1 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y + 1][x] +
          matrix[y + 2][x] +
          matrix[y + 1][x + 1]
      );
    // ㅓ
    if (y + 2 < N && x - 1 > 0)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y + 1][x] +
          matrix[y + 2][x] +
          matrix[y + 1][x - 1]
      );
    // ㅗ
    if (y + 1 < N && x + 2 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y][x + 1] +
          matrix[y][x + 2] +
          matrix[y + 1][x + 1]
      );
    // ㅜ
    if (y > 0 && x + 2 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y][x + 1] +
          matrix[y][x + 2] +
          matrix[y - 1][x + 1]
      );
  }
JavaScript
복사

스터디원 풀이

현위치 제외하고 각 모양마다 필요한 좌표는 3개씩있다.

tx와 ty는 한쌍이 된다. (1,0), (2,0), (1,1)

회전, 대칭 포함 총 모양이 4개다.

https://velog.io/@skyepodium/백준-14500-테트로미노

Code

const solution = function (i) {
  const [[N, M], ...matrix] = i
    .toString()
    .trim()
    .split('\n')
    .map((v, i) =>
      i === 0 ? v.split(' ').map(Number) : v.split(' ').map(v => +v)
    );

  let result = Number.MIN_SAFE_INTEGER;
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  function DFS(y, x, depth, sum, visit) {
    if (depth >= 4) {
      result = Math.max(result, sum);
      return;
    }

    for (let k = 0; k < 4; k++) {
      const ny = y + dy[k];
      const nx = x + dx[k];

      if (!(ny < 0 || nx < 0 || ny >= N || nx >= M || visit[ny][nx])) {
        visit[ny][nx] = true;
        DFS(ny, nx, depth + 1, sum + matrix[ny][nx], visit);
        visit[ny][nx] = false;
      }
    }
  }

  function checkEdgeCaseSum(y, x) {
    // ㅏ
    if (y + 2 < N && x + 1 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y + 1][x] +
          matrix[y + 2][x] +
          matrix[y + 1][x + 1]
      );
    // ㅓ
    if (y + 2 < N && x - 1 > 0)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y + 1][x] +
          matrix[y + 2][x] +
          matrix[y + 1][x - 1]
      );
    // ㅗ
    if (y + 1 < N && x + 2 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y][x + 1] +
          matrix[y][x + 2] +
          matrix[y + 1][x + 1]
      );
    // ㅜ
    if (y > 0 && x + 2 < M)
      result = Math.max(
        result,
        matrix[y][x] +
          matrix[y][x + 1] +
          matrix[y][x + 2] +
          matrix[y - 1][x + 1]
      );
  }

  const visit = new Array(N).fill(false).map(() => new Array(M).fill(false));
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      visit[i][j] = true;
      DFS(i, j, 1, matrix[i][j], visit);
      visit[i][j] = false;
      checkEdgeCaseSum(i, j);
    }
  }

  console.log(result);
  return result;
};

describe('테트로미노', () => {
  it('TC1', () => {
    expect(
      solution(`5 5
1 2 3 4 5
5 4 3 2 1
2 3 4 5 6
6 5 4 3 2
1 2 1 2 1`)
    ).toStrictEqual(19);
  });
  it('TC2', () => {
    expect(
      solution(`4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5`)
    ).toStrictEqual(20);
  });
  it('TC3', () => {
    expect(
      solution(`4 10
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1
1 2 1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1 2 1`)
    ).toStrictEqual(7);
  });
});
JavaScript
복사