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

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

14500번: 테트로미노

풀이

도형을 일일히 만들어서 회전, 대칭시키기에는 답이 없고... 브루트포스 밖에 없겠는데 라고 생각하다가 DFS로 구현했다. 시간제한도 2초라서 문제 없을 듯 했다.

1. DFS로 시작점을 포함해 4번 동안 연결 가능한 모든 사각형에 대해 검사한다.

2. 이때, 4방향에 대해서만 DFS를 돌리면 뻐큐모양(?)에 대해서는 검사할 수 없으므로, 8방향 모두 체크 배열을 사용해서 검사하고자 하는 영역의 옆에 이미 체크한 정사각형이 있는지(인접 존재 체크) 검사한다. 

3. 4번 연결이 끝나면 백트래킹 방식으로 체크 해제 해주면서 모든 시작점에 대해 검사해주면 답을 구할 수 있다. 

리뷰

어려워 보이지만 조금만 단순히 생각하면 어렵지 않은 문제였다.

#include <iostream>
#include <vector>

using namespace std;

int N, M, ans; 
int map[502][502];
int ch[502][502];
int dr[8] = {0, 1, 0, -1, -1, 1, 1, -1};
int dc[8] = {1, 0, -1, 0, 1, 1, -1, -1};
/*
테트로미노 하나로 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램
회전, 대칭 가능
현 위치에서 dfs로 연결 가능한 모든 도형 탐색, 정답 업데이트
*/

void DFS(int L, int sum, int row, int col)
{
    if (L==3){
        ans = max(ans, sum);
    }
    else {
        for (int i=0; i<7; i++){
            int nr = row + dr[i];
            int nc = col + dc[i];

            if (nr < 1 || nr > N || nc < 1 || nc > M) continue;
            
            if (!ch[nr][nc]){
                // 인접 존재 체크
                if (ch[nr][nc+1]==1 || ch[nr+1][nc]==1 ||
                ch[nr][nc-1]==1 || ch[nr-1][nc]==1){
                    ch[nr][nc]=1;
                    DFS(L+1, sum+map[nr][nc], nr, nc);
                    ch[nr][nc]=0;
                }
                
            }
        }
        
    }
};

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

    // freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            cin >> map[i][j]; 
        }
    }

    for (int i=1; i<=N; i++){
        for (int j=1; j<=M; j++){
            ch[i][j]=1;
            DFS(0, map[i][j], i, j);
            ch[i][j]=0;
        }
    }

    cout << ans << endl;
    return 0;
}