[백준] 14500: 테트로미노 (with C++)

음, BFS로 풀려다가 메모리 초과났다. 종이 크가기 500 이하의 가로세로인데, 이게 꽤 커서 BFS는 안됐다. 조건을 좀 더 꼼꼼히 볼 필요가 있다...

또, 어떤 글에서 벡터를 array에 저장하는 방식으로 동서남북 블록을 탐색하는 것을 봤는데, 아주 괜찮은 것 같다. 아주 좋다. 가능한 노드들 탐색할 때 나도 이렇게 해야겠다.

 

문제

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

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

14500번: 테트로미노

 

구상

1. 가능한 모든 경우를 탐색해야 한다.

2. 깊이 4 제한의 DFS, 각 폴리오미노가 이번 가지에서 방문되었는지 체크해서, 각 가능한 방향의 폴리오미노에 대해 대해 방문되지 않았으면서 범위 안이면 그쪽으로 연결해서 계속 판다.

3. 깊이 4면 중단 후 max값 저장한다.

4. 2~3 과정을 모든 보드의 폴리오미노에 대해 반복한다. 

4. ㅗ,ㅏ,ㅜ,ㅓ 모양은 따로 탐색한다.(이건 DFS 아님, 그냥 브루트 포스로 확인한다.)

 

코드

#include<iostream>
#include<queue>
#include<vector>

using namespace std;
int dx[4] = {0,0,1,-1}; //right, left, up, down
int dy[4] = {1,-1,0,0}; //right, left, up, down

int ox[4][4] = {{0,0,0,1}, {0,0,0,-1}, {0,1,2,1}, {0,1,2,1}}; // ㅜ ㅗ ㅏ ㅓ
int oy[4][4] = {{0,1,2,1}, {0,1,2,1}, {0,0,0,1}, {0,0,0,-1}}; // ㅜ ㅗ ㅏ ㅓ

bool** check;
int** board;    
int N, M;
int result;


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

    if(depth == 4) {
        result = max(result, sum);
        return;
    }

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

        if(new_x <0 || new_y < 0 || new_x >= N || new_y >= M || check[new_x][new_y]) {
            continue;
        }
        
        check[new_x][new_y] = true;
        dfs(new_x, new_y, sum + board[new_x][new_y], depth + 1);
        check[new_x][new_y] = false;
    }
}

void check_O(int x, int y) {
    for(int i=0; i<4; i++) {
        bool valid = true;
        int sum = 0;
        for(int j=0; j<4; j++) {
            int new_x = x + ox[i][j];
            int new_y = y + oy[i][j];
            
            if(new_x < 0 || new_y < 0 || new_x >= N || new_y >= M) {
                valid = false;
                break;
            }
            sum += board[new_x][new_y];
        }
        if(valid){
            result = max(sum, result);
        }
    }
}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    board = new int*[N];
    check = new bool*[N];
    result = -1;

    for(int i=0; i<N; i++) {
        board[i] = new int[M];
        check[i] = new bool[M];
        for(int j=0; j<M; j++) {
            cin >> board[i][j];
            check[i][j] = false;
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            check[i][j] = true;
            dfs(i, j, board[i][j], 1);
            check[i][j] = false;
            check_O(i, j);
        }
    }
    
    
    cout << result << "\n";

	return 0;
}

코드가 내 편집창에서는 알록달록한데 포스팅을 올리면 칙칙해진다.