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

1. 문제

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

14500번: 테트로미노

2. 풀이과정

문제에서 주어지는 N×M 종이 위에 테트로미노 하나를 놓을 수 있는 모든 경우를 탐색하며 

테르토미노가 놓인 칸에 쓰여있는 수들의 합을 계산해 최대값을 구한다.

 

처음 문제를 풀 때 가장 단순한 방법으로, 5개의 테트로미노를 배열로 나타낸 후

각각 직접 회전, 대칭시키며 가능한 모든 경우를 탐색해보았는데 시간초과가 났다.

 

사실 테트로미노의 모양을 보면, ㅜ모양을 제외하고 나머지 모양들은 

한 정점에서 출발하여 상하좌우로 움직일 수 있으며 총 4개의 정점을 방문하는 dfs를 이용하여

모양들의 회전, 대칭까지 모든 경우를 탐색할 수 있다.

 

ㅜ모양은 예외적으로 따로 처리해주면 된다.

 

[코드설명]

tetrominos배열은 ㅜ모양으로 탐색할 수 있는 ㅜ, ㅏ, ㅗ, ㅓ 모양을 배열로 나타낸 것이다.

 

dfs함수는 특정 점에서 ㅜ모양을 제외한 나머지 모양을 종이에 놓을 수 있는 모든 경우에 대해 탐색한다.

 

tetro함수는 특정 점에서 ㅜ, ㅏ, ㅗ, ㅓ 모양을 종이에 놓는 경우에 대해 탐색한다. 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m;
vector<vector<int>> board;
int max_v = -1;
bool visited[510][510];
int dy[4] = {-1, 0, 0, 1}, dx[4] = {0, -1, 1, 0};
int tetrominos[4][4][2] = {
    {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
    {{0, 0}, {1, 0}, {2, 0}, {1, 1}},
    {{0, 0}, {0, 1}, {0, 2}, {-1, 1}},
    {{0, 0}, {-1, 1}, {0, 1}, {1, 1}},
};

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

void tetro(int y, int x) {
    for(int i=0; i<4; i++) {
        int sum = 0, safe_cnt = 0;
        for(int j=0; j<4; j++) {
            int ny = y + tetrominos[i][j][0];
            int nx = x + tetrominos[i][j][1];
            if(safe(ny, nx)) {
                safe_cnt++;
                sum += board[ny][nx];
            }
        }
        if(safe_cnt == 4) max_v = max(max_v, sum); 
    }
    return ;
}

void dfs(int y, int x, int depth, int sum) {
    if(depth == 3) {
        max_v = max(max_v, sum);
        return ;
    }
    for(int i=0; i<4; i++) {
        int ny = y + dy[i], nx = x + dx[i];
        if(safe(ny, nx) && !visited[ny][nx]) {
            visited[ny][nx] = true;
            dfs(ny, nx, depth+1, sum+board[ny][nx]);
            visited[ny][nx] = false;
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    board.resize(n);
    for(int i=0; i<n; i++) {
        board[i].resize(m);
        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++) {
            visited[i][j] = true;
            dfs(i, j, 0, board[i][j]);
            tetro(i, j);
            visited[i][j] = false;
        }
    }
    cout << max_v;
    return 0;
}