[백준] 14500 테트로미노 c++

처음에는 bfs로 5개의 테트로미노의 대칭과 회전 모양 모두를 고려해야 하는 줄 알았다. 시도해보다가 좀 말이 안된다는 생각이 들었다. 어떻게 할까 생각하다가 구글링을 통해 ㅗ모양의 테트로미노를 제외한 모든 테트로미노가 depth를 4로 하는 bfs(혹은 dfs)모양이라는 것이었다.

 

이 힌트를 토대로 모든 좌표를 돌면서 dfs를 depth 4까지만 수행하였다.

그리고 dfs와 함께 추가적으로 ㅗ모양 테트로미노에 대한 점수 카운팅도 해주었다.

 

ㅗ모양 테트로미노 점수계산시에, 2중 for문을 통해 상하좌우 중 무시할 방향을 한군데씩 골라 계산하게 되면 딱 ㅗ ㅜ ㅏ ㅓ 테트로미노를 모두 고려할 수 있다.

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int board[502][502] ={0,}; // 0~501 1~500에 저장.
int v[502][502] ={0,};
int answer = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int isPass(int x, int y){
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

void dfs(int x, int y, int score, int depth){
    if(depth==4){
        answer = max(answer, score);
        return;
    }

    for (int i = 0; i < 4; i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (isPass(tx, ty) && v[tx][ty] == 0)
        {
            v[tx][ty] = 1;
            dfs(tx, ty, score+board[tx][ty], depth+1);
            v[tx][ty] = 0;
        }
    }
}

void blockChect(int x, int y){
    for (int i = 0; i < 4; i++){
        // i - 무시할 방향.
        int score = board[x][y];
        for (int j = 0; j < 4; j++)
        {
            int tx = x + dx[j];
            int ty = y + dy[j];
            if(i != j){
                score += board[tx][ty];
            }
        }
        answer = max(answer, score);
    }
    return;
}

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

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

    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            v[i][j]=1;
            dfs(i, j, board[i][j], 1);
            v[i][j]=0;

            blockChect(i, j);
        }
    }

    cout << answer << endl;

    return 0;
}

 

ps. 처음에는 dfs가 아닌 bfs로 짜다가 queue안의 요소가 너무 복잡해졌다. 그래서 tuple을 이용해 x,y좌표, 점수, 깊이, 방문배열을 넣었는데 tuple안에는 int 배열을 넣을 수 없는 모양이였다..