[Baekjoon]백준 14500번 테트로미노

14500번 테트로미노 문제 풀이

문제

• 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
  1. 정사각형은 서로 겹치면 안된다.
  2. 도형은 모두 연결되어 있어야 한다.
  3. 정사각형의 꼭짓점끼리 연결되어 있어야 한다.
• 아름이는 크기가 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
----------------
4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
----------------
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

출력 

19 
20
7

해결방법

변수명	내용
maze	정수가 쓰여진 배열
check	탐색 여부를 확인하기 위한 배열
dx, dy	다음 칸 탐색을 위해 x,y값을 증감하는 배열
result	최대 값을 저장시키는 변수
n , m	행, 열 입력

• 보라색 도형을 제외한 나머지 도형들은 회전 및 대칭을 시켜도 DFS로 구현할 수 있다.

• 따라서 DFS탐색을 하는 함수와 보라색 도형으로 만들 수 있는 모든 모양의 도형을 탐색할 수 있는 함수 exshape를 구현한다.

    void dfs(int i, int j, int cnt, int sum) {
        result = max(result, sum);
        if (cnt == 4) {
            return;
        }
        for (int k = 0; k < 4; k++) {
            int nx = i + dx[k];
            int ny = j + dy[k];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m&& check[nx][ny] != 1){
                check[nx][ny] = 1;
                dfs(nx, ny, cnt + 1, sum + maze[nx][ny]);
                check[nx][ny] = 0;
            }
        }
    }

  • 인자 값으로 x좌표, y좌표, 탐색한 칸의 수, 정수들의 합 4가지를 받는다.

  • 첫 번째 칸을 탐색하게 되면 x,y좌표를 증감하여 다음 칸으로 이동시킨다. 이 때 cnt는 1씩 증가하며 sum은 다음 좌표에 적혀있는 정수값을 더해주게 된다.

  • 현재 위치에서 다음 위치로 탐색할 수 있는 범위를 모두 탐색했을 시 재귀된 dfs는 종료되며 check배열의 본인 위치는 다시 0으로 되돌린다.

    void exshape(int x, int y) {
      // ㅓ
      if (x - 1 >= 0 && x < n && y + 2 < m && y >= 0) {
          result = max(result, maze[x][y] + maze[x - 1][y + 1] + maze[x][y + 1] + maze[x][y + 2]);
      }
      // ㅜ
      if (x >= 0 &&x+2 < n &&y - 1 >= 0 && y < m) {
          result = max(result, maze[x][y] + maze[x + 1][y] + maze[x + 2][y] + maze[x + 1][y - 1]);
      }
      // ㅗ
      if (x >= 0 && x + 2 < n && y + 1 < m && y >= 0) {
          result = max(result, maze[x][y] + maze[x + 1][y] + maze[x + 2][y] + maze[x + 1][y + 1]);
      }
      // ㅏ
      if (x >= 0 && x+1 < n && y + 2 < m && y >= 0) {
          result = max(result, maze[x][y] + maze[x][y + 1] + maze[x][y + 2] + maze[x + 1][y + 1]);
      }
    }

  • 보라색 도형은 DFS로 불가하기 때문에 모든 모양들에 대해 직접 좌표를 계산한다.

  • X와 Y의 범위를 설정할 시 증감되는 범위를 생각해야한다.

코드

#include<iostream>
#include<algorithm>
using namespace std;

int maze[501][501];
int check[501][501];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int result = 0;
int n, m;

void dfs(int i, int j, int cnt, int sum) {
    result = max(result, sum);
    if (cnt == 4) {
        return;
    }
    for (int k = 0; k < 4; k++) {
        int nx = i + dx[k];
        int ny = j + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m&& check[nx][ny] != 1){
            check[nx][ny] = 1;
            dfs(nx, ny, cnt + 1, sum + maze[nx][ny]);
            check[nx][ny] = 0;
        }
    }
}
void exshape(int x, int y) {
    // ㅓ
    if (x - 1 >= 0 && x < n && y + 2 < m && y >= 0) {
        result = max(result, maze[x][y] + maze[x - 1][y + 1] + maze[x][y + 1] + maze[x][y + 2]);
    }
    // ㅜ
    if (x >= 0 &&x+2 < n &&y - 1 >= 0 && y < m) {
        result = max(result, maze[x][y] + maze[x + 1][y] + maze[x + 2][y] + maze[x + 1][y - 1]);
    }
    // ㅗ
    if (x >= 0 && x + 2 < n && y + 1 < m && y >= 0) {
        result = max(result, maze[x][y] + maze[x + 1][y] + maze[x + 2][y] + maze[x + 1][y + 1]);
    }
    // ㅏ
    if (x >= 0 && x+1 < n && y + 2 < m && y >= 0) {
        result = max(result, maze[x][y] + maze[x][y + 1] + maze[x][y + 2] + maze[x + 1][y + 1]);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n;i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
            check[i][j] = 0;
        }
    }

    for (int i = 0; i <n; i++) {
        for (int j = 0; j <m; j++) {
            check[i][j] = 1;
            dfs(i, j, 1, maze[i][j]);
            exshape(i, j);
            check[i][j] = 0;
        }
    }

    cout << result << '\n';
    return 0;
}