[C++] 백준 14500 | 테트로미노

테트로미노

14500번: 테트로미노

---

✍🏻 풀이

정사각형 4개를 이어 붙인 도형을 테트로미노라고 한다.

이 테트로미노는 위와 같이 총 5가지의 경우의 수로 나뉜다. (회전, 대칭 가능)
이 문제를 보고 DFS나 BFS로 풀면 간단하게 풀릴 거라고 생각했지만, 주의할 점이 있다.
언뜻 봤을 땐 깊이 4로 탐색하면 되지만 우리가 주목해야 할 건 'T' 모양의 테트로미노다. (ㅏ, ㅓ, ㅗ, ㅜ)
이 모양은 나머지 모양과 별개로 따로 탐색해주어야 한다!

또 주의해야 할 점은 주어진 배열의 범위가 크기 때문에 시간초과가 날 수 있다.
visited 배열을 이용하여 중복 체크를 해주어야 하며,
네 칸의 합을 구할 때도 배열 전체를 탐색하는 방법 대신 함수의 인자로 sum 변수를 넘겨주었다.

 

---

✅ Accept Code

// baekjoon 14500

#include <bits/stdc++.h>

using namespace std;


int N, M;
int paper[500][500];
bool visited[500][500];
int ans = 0;

int di[4] = {0, 0, 1, -1};
int dj[4] = {1, -1, 0, 0};

void DFS(int i, int j, int cnt, int sum) {
    if (cnt == 4) {
        ans = max(ans, sum);
        return;
    }

    for (int idx = 0; idx < 4; idx++) {
        int new_i = i + di[idx];
        int new_j = j + dj[idx];

        if (new_i < 0 || new_i > N - 1 || new_j < 0 || new_j > M - 1) continue;
        if (visited[new_i][new_j]) continue;

        visited[new_i][new_j] = true;
        DFS(new_i, new_j, cnt + 1, sum + paper[new_i][new_j]);
        visited[new_i][new_j] = false;
    }
}

// ㅏ, ㅓ, ㅗ, ㅜ 모양 탐색
void findTShape(int i, int j) {
    int east = j + 1;
    int west = j - 1;
    int south = i + 1;
    int north = i - 1;

    // ㅏ
    if (east < M && south < N && north >= 0) {
        int sum = paper[i][j] + paper[i][east] + paper[north][j] + paper[south][j];
        ans = max(sum, ans);
    }

    // ㅓ
    if (west >= 0 && south < N && north >= 0) {
        int sum = paper[i][j] + paper[i][west] + paper[north][j] + paper[south][j];
        ans = max(sum, ans);
    }

    // ㅗ
    if (east < M && west >= 0 && north >= 0) {
        int sum = paper[i][j] + paper[i][east] + paper[i][west] + paper[north][j];
        ans = max(sum, ans);
    }

    // ㅜ
    if (east < M && west >= 0 && south < N) {
        int sum = paper[i][j] + paper[i][east] + paper[i][west] + paper[south][j];
        ans = max(sum, ans);
    }
}


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

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> paper[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visited[i][j] = true;
            DFS(i, j, 1, paper[i][j]);
            visited[i][j] = false;
            findTShape(i, j);
        }
    }
    cout << ans;
}