[백준/C++] 14500번: 테트로미노

문제

https://www.acmicpc.net/problem/14500

---

문제 요약

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

 

1. 정사각형은 서로 겹치면 안 된다.

2. 도형은 모두 연결되어 있어야 한다.

3. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

 

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

 

 

N × M 크기의 격자 종이에 테트로미노 하나를 놓으려고 할 때,

테트로미노가 놓인 칸에 쓰인 수들의 합을 최대를 출력한다.

---

코드

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

int board[550][550];
bool visited[550][550];

int n, m;

int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int res;

void dfs(int x, int y, int cnt, int sum) {

    if (cnt == 4) {
        res = max(res, sum + board[x][y]);
        return;
    }

    visited[x][y] = true;

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

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (visited[nx][ny]) continue;

        dfs(nx, ny, cnt + 1, sum + board[x][y]);
    }

    visited[x][y] = false;
}

int main() {
    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, 1, 0);
        }
    }

    // ㅜ
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 2; j++) {
            res = max(res, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1]);
        }
    }

    // ㅏ
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m - 1; j++) {
            res = max(res, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1]);
        }
    }

    // ㅗ
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m - 2; j++) {
            res = max(res, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i - 1][j + 1]);
        }
    }

    // ㅓ
    for (int i = 1; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            res = max(res, board[i][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i - 1][j + 1]);
        }
    }
    

    cout << res;


    return 0;
}

---

코드 설명

'ㅗ', 'ㅏ', 'ㅜ', 'ㅓ' 모양은 모든 경우의 수를 직접 확인하여 합을 구하고,

 

나머지 모양은 DFS를 이용하여 경우의 수를 확인한다.

이 때, 시작점을 (0, 0)부터 (n - 1, m - 1)까지 모든 점을 잡고 DFS를 진행한다.