문제

문제 유형: 구현 브루트포스 알고리즘
난이도: 골드Ⅳ

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

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

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

풀이

위 테트로미노를 자세히 보면 모두 정사각형 4개로 이루어져 있다.
모두 한 점에서 시작해서 3칸 이동하면 구할 수 있는 모양인 것이다.
여기서, 깊이가 4인 DFS 탐색이라는 아이디어를 얻을 수 있다.

모든 정점에 대해서 깊이가 4인 DFS 탐색을 진행했을 때 나오는 가장 큰 값이 테트로미노의 최댓값이 되는 것이다.

예외

하지만 예외가 있다.
ㅜ 모양은 DFS로 구할 수 없다.
회전 하는 경우까지 포함하면 ㅜ, ㅓ, ㅗ, ㅏ 모두 예외이다.
그렇다면 어떻게 구할 수 있을까?

' + ' 모양이 있다고 했을 때, 가운데 점을 선택하고 주변 4개의 정사각형 중 숫자가 가장 작은 것을 제외한 3개를 선택하면 해당 테트로미노로 만들 수 있는 최댓값을 구할 수 있다.

따라서 이렇게 구한 값과 DFS로 구한 값 중 더 큰 것이 정답이다.

✨ 주의할 점
DFS로 탐색 할 때 방문한 지점을 체크해주는데, 이때는 정상적인 작동이 되지 않으므로 한번 완료하고 나면 백트래킹을 해준다.

코드

#include <iostream>
using namespace std;

int n, m, ans;
int paper[555][555];
int visited[555][555];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, 1, 0, -1};
void dfs(int y, int x, int cnt, int val) {
    if (cnt == 4) ans = ans < val ? val : ans;
    else {
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i]; int nx = x + dx[i];
            if (ny < 1 or ny > n or nx < 1 or nx > m) continue;
            if (visited[ny][nx]) continue;
            visited[ny][nx]++;
            dfs(ny, nx, cnt + 1, val + paper[ny][nx]);
            visited[ny][nx]--;
        }
    }
}
int main() {
    ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> paper[i][j];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            visited[i][j]++;
            dfs(i, j, 1, paper[i][j]);
            visited[i][j]--;
        }
    } 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int t = paper[i][j]; // 보라색 테트로미노의 가운데를 표시한다
            int mini = 1001;
            for (int k = 0; k < 4; k++) {
                mini = mini < paper[i + dy[k]][j + dx[k]] ? mini : paper[i + dy[k]][j + dx[k]]; // 가운데 점의 상하좌우에 있는 값 중에 최소의 값을 나타낸다
                t += paper[i + dy[k]][j + dx[k]]; // 상하좌우에 있는 값을 모두 더한다. 그러면 십자가 모양처럼 되니 테트로미노가 아니다
            }
            ans = ans < t - mini ? t - mini : ans; // 상하좌우에 있는 값 중 최소 값을 제거한다. 그러면 보라색 테트로미노의 모양이 된다
        }
    } 
    cout << ans;
    return 0;
}