[BOJ #14500] 테트로미노

문제 설명

문제 링크
$n*m$ 크기의 직사각형 종이가 주어지고 종이는 $1*1$ 크기의 정사각형으로 이루어져 있다.
각 정사각형엔 수가 적혀있고 테트로미노 도형으로 정사각형들을 가릴 때 가려진 정사각형에 적힌 수들의 합의 최대값을 구하는 문제이다.

알고리즘

첫 번째 접근 방법은 이러했다.
각 테트로미노는 4개의 정사각형으로 이루어져 있고 연결되어 있으니 DFS로 각 시작 지점에서 크기가 4인 모양을 탐색하면 될 거라 생각했다.

이렇게 구현해놓고 보니 테트로미노 중 'ㅗ' 모양을 탐색할 수 없는 문제점이 발생했다.
그래서 ㅗ모양은 따로 다시 구현해서 해결해주었다.

추가로 중복해서 탐색하는 부분이 많다는 걸 인지하고 있었는데 시간 제한이 크게 부족하진 않아서dx[], dy[]부분에서 상하좌우로 이동할 수 있던 걸 상하우(좌를 뺌)로만 이동하게 해서 중복 부분을 조금 줄였는데 시간에 큰 영향은 못끼친 듯 하다.

220627 수정
코드를 새로 짜면서 중복 탐색 부분은 최적화는 하지 않았습니다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
int ans = 0;
int board[500][500];
const int dx[] = {1, 0, 0};
const int dy[] = {0, 1, -1};
bool visited[500][500];

const int a[4][4] = {
        {0, 1, 1, 2}, {0, 1, 1, 2}, {0, 0, 0, 1}, {0, 0, 0, -1}
};
const int b[4][4] = {
        {0, 0, 1, 0}, {0, 0, -1, 0}, {0, 1, 2, 1}, {0, 1, 2, 1}
};

bool InRange(int y, int x) {
    return (0 <= y && y < n && 0 <= x && x < m);
}

void Dfs(int y, int x, int n, int sum) {
    visited[y][x] = true;
    sum += board[y][x];
    n++;
    if (n == 4) {
        ans = max(ans, sum);
        visited[y][x] = false;
        return;
    }

    for (int i = 0; i < 3; ++i) {
        int ny = y + dy[i], nx = x + dx[i];
        if (!InRange(ny, nx)) continue;
        if (visited[ny][nx]) continue;

        Dfs(ny, nx, n, sum);
    }
    visited[y][x] = false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> board[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            Dfs(i, j, 0, 0);
        }
    }


    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < 4; ++k) {
                bool flag = true;
                int s = 0;
                for (int l = 0; l < 4; ++l) {
                    if (!InRange(i + a[k][l], j + b[k][l])) {
                        flag = false;
                        break;
                    }
                    s += board[i + a[k][l]][j + b[k][l]];
                }

                if (flag) ans = max(ans, s);
            }
        }
    }


    cout << ans << '\n';
}

느낀점...

코드를 다시 짜면서 느낀 점이지만 가독성 좋게 코드 짜는 게 참 어려운 일인거 같다. 변수명도 최대한 자세히 쓰려 했는데 기존 코드보다 조금 나아진 거에 만족해야겠다... 다음엔 더 좋은 코드를 짤 수 있겠지