[백준알고리즘] 14500 테트로미노

테트로미노

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	4276	1315	919	29.770%

문제

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

• 정사각형은 서로 겹치면 안된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 꼭지점끼리 연결되어 있어야 한다. 즉, 변과 꼭지점이 맞닿아있으면 안된다.

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

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

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

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

입력

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

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

출력

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

예제 입력

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

예제 출력

19

예제 입력 2

4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

예제 출력 2

20

 

 

 

#include <stdio.h>

 

int N, M, result;
int map[500][500];
bool visit[500][500];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

 

void dfs1(int x, int y, int n, int sum)
{
 if (n == 4)
 {
  if (result < sum) result = sum;
  return;
 }

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

  if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
  if (visit[nx][ny]) continue;

  visit[nx][ny] = true;
  dfs1(nx, ny, n + 1, sum + map[nx][ny]);
  visit[nx][ny] = false;
 }

 return;
}

void dfs2(int x, int y, int n, int sum)
{
 if (n == 4)
 {
  if (result < sum) result = sum;
  return;
 }

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

  if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
  if (visit[nx][ny]) continue;

  visit[nx][ny] = true;
  dfs2(x, y, n + 1, sum + map[nx][ny]);
  visit[nx][ny] = false;

 }

 return;
}

int main()
{
 scanf("%d%d", &N, &M);
 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
  {
   scanf("%d", &map[i][j]);
   visit[i][j] = false;
  }

 result = 0;

 for (int i = 0; i < N; i++)
  for (int j = 0; j < M; j++)
  {
   visit[i][j] = true;
   dfs1(i, j, 1, map[i][j]);
   dfs2(i, j, 1, map[i][j]);
   visit[i][j] = false;
  }

 printf("%d\n", result);

 return 0;
}