백준 14500번 [테트로미노](C++) -yes6686- 티스토리

백준 문제 풀이: 14500 [테트로미노]

---

문제 링크: https://www.acmicpc.net/problem/14500

문제 설명:

n×m 크기의 격자판이 주어질 때, 테트로미노를 격자판에 놓아 얻을 수 있는 최대 합을 구하는 문제입니다. 테트로미노는 총 5가지 모양(4개 정점으로 이루어진 다양한 배치)을 가집니다. 모든 경우를 탐색하여 최대 합을 구해야 합니다.

입력:

• 첫째 줄에 n(1 ≤ n ≤ 500)과 m(1 ≤ m ≤ 500)이 주어집니다.
• 둘째 줄부터 n개의 줄에 격자판의 값이 주어집니다. (1 ≤ 값 ≤ 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

출력:
19

---

문제 해결 코드

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

int n, m;
int arr[505][505];
bool visited[505][505];
int maxSum = 0;

// 상하좌우 방향 이동
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

// DFS로 최대값 탐색
void dfs(int x, int y, int depth, int sum) {
    if (depth == 4) { // 블록 4개를 모두 탐색한 경우
        maxSum = max(maxSum, sum);
        return;
    }

    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !visited[nx][ny]) {
            dfs(nx, ny, depth + 1, sum + arr[nx][ny]);
        }
    }

    visited[x][y] = false;
}

// ㅗ, ㅜ, ㅓ, ㅏ 모양 테트로미노 처리
void checkTShape(int x, int y) {
    if (x >= 1 && x + 1 <= n && y - 1 >= 1 && y + 1 <= m) {
        maxSum = max(maxSum, arr[x][y] + arr[x][y - 1] + arr[x][y + 1] + arr[x + 1][y]); // ㅜ
    }
    if (x - 1 >= 1 && x + 1 <= n && y + 1 <= m) {
        maxSum = max(maxSum, arr[x][y] + arr[x - 1][y] + arr[x + 1][y] + arr[x][y + 1]); // ㅏ
    }
    if (x - 1 >= 1 && x + 1 <= n && y - 1 >= 1) {
        maxSum = max(maxSum, arr[x][y] + arr[x - 1][y] + arr[x + 1][y] + arr[x][y - 1]); // ㅓ
    }
    if (x - 1 >= 1 && y - 1 >= 1 && y + 1 <= m) {
        maxSum = max(maxSum, arr[x][y] + arr[x - 1][y] + arr[x][y - 1] + arr[x][y + 1]); // ㅗ
    }
}

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

    cin >> n >> m;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j, 1, arr[i][j]); // DFS로 테트로미노 탐색
            checkTShape(i, j); // ㅗ 모양 처리
        }
    }

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

---

코드 설명

이 코드는 DFS와 직접적인 모양 탐색을 조합하여 테트로미노의 모든 경우를 처리합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • DFS를 사용하여 4개의 칸을 탐색하며 테트로미노의 최대 합을 구합니다.
  • ㅗ 모양은 DFS로 처리하기 어려우므로 별도로 구현하여 검사합니다.
• 구현 세부사항:
  • dfs(x, y, depth, sum): 현재 위치에서 가능한 모든 방향으로 탐색합니다.
  • checkTShape(x, y): ㅗ, ㅜ, ㅓ, ㅏ 모양의 테트로미노를 직접 계산합니다.
• 시간 복잡도 분석:
  • DFS: O(n * m)
  • 모든 좌표에서 ㅗ 모양 검사: O(n * m)
  • 총 시간 복잡도: O(n * m)

---

결과

코드는 격자판의 모든 경우를 완전 탐색하여 테트로미노의 최대 합을 계산합니다. 입력 크기에 따라 적절한 성능을 제공합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!