[14500번] 테크로미노

문제

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

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

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

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

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

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

 

문제접근법.

1. 도형들을 만드는 것은 4방향으로 탐색하는 Depth가 4인 Backtracking을 하는 것이다.

2. 백트래킹으로 만들 수 없는 도형들이 존재한다.

 

백트래킹 함수를 작성해야 한다. 백트래킹 함수가 작성 및 이해가 어려운 사람들은 한 가지만 기억하면 된다.

 

'백트래킹은 백트래킹을 하는 함수를 재귀적으로 호출 하는 것이다.'

 

컴퓨터 알고리즘을 처음 접한 사람들은 재귀적 사고의 이해가 많이 힘들 수 있다. 이 부분이 이해가 잘되지 않는다면, 기본적인 피보나치 재귀 함수를 기반으로 이해하는 것을 추천한다.

 

 백트래킹으로 만들 수 없는 도형들이 존재한다, 백트래킹은 만들어진 도형을 기반으로 다시 그 도형으로 돌아오지 않는다. 백트래킹만으론 예제의 5번째 도형(ㅜ)을 만들 수 없다. 이 부분에 대해서 백트래킹과 별개로 검사해주는 것이 필요하다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int op[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;
int map[501][501];
int check[501][501];
int answer = 0;
int result = 0;
 
void dfs(int r, int c, int cnt) {
    if (cnt == 4) {
        answer = max(answer, result);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        int n_r = r + op[i][0];
        int n_c = c + op[i][1];
 
        if (n_r < 1 || n_r > N || n_c < 1 || n_c > M || check[n_r][n_c] == 1)
            continue;
 
        check[n_r][n_c] = 1;
        result += map[n_r][n_c];
        dfs(n_r, n_c, cnt + 1);
        result -= map[n_r][n_c];
        check[n_r][n_c] = 0;
    }
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N >> M;
    memset(check, 0, sizeof(check));
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
 
    // Backtracking
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            dfs(i, j, 0);
        }
    }
 
    // Not Backtracking #1
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M - 2; j++) {
            int temp = map[i][j] + map[i][j + 1] + map[i][j + 2];
            if (i - 1 >= 1) {
                answer = max(answer, temp + map[i - 1][j + 1]);
            }
            if (i + 1 <= N) {
                answer = max(answer, temp + map[i + 1][j + 1]);
            }
        }
    }
 
    // Not Backtracking #2
    for (int i = 1; i <= N - 2; i++) {
        for (int j = 1; j <= M; j++) {
            int temp = map[i][j] + map[i + 1][j] + map[i + 2][j];
            if (j + 1 <= M) {
                answer = max(answer, temp + map[i + 1][j + 1]);
            }
            if (j - 1 >= 1) {
                answer = max(answer, temp + map[i + 1][j - 1]);
            }
        }
    }
 
    cout << answer << endl;
    return 0;
}