[백준] 14500 - 테트로미노

이 문제 역시 삼성기출로 나왔다는 문제

문제에서 주어진 테트로미노를 검사하고, 그 영역안에 값을 모두 더했을 때 최대값을 구하는 문제

인접한 4개를 고르는 것이기 때문에 dfs로 4개를 골라 검사해주면 끝

하지만, 주어진 테트로미노 중 ㅏ모양과 이를 회전시킨 ㅗ ㅓ ㅜ 까지 총 4개는 따로 검사해야 한다

1. dfs로 4개를 골라 최대값을 찾는다

2. 그 지점에서 ㅏ ㅗ ㅓ ㅜ 4개의 모양을 검사하여 최대값을 찾는다

1번 같은 경우는 사실 너무 정형화된 형태라 세부 코딩만 다르고 왠만하면 모두 똑같이 풀 수 있다

하지만 2번같은 경우는 사람마다 더 효율적인 코딩이 되도록 짤수도 있고, 그냥 나처럼 방향 모두 구하고 범위검사하고 해도 시간은 충분하다

#include <iostream>
#define MX 502
using namespace std;
 
int map[MX][MX], check[MX][MX];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, -1, 0, 1 };
int N, M, dab;
 
void dfs(int d, int x, int y, int sum)
{
    if (d == 4)
    {
        if (sum > dab) dab = sum;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= M || ny >= N || check[ny][nx]) continue;
        check[ny][nx] = 1;
        dfs(d + 1, nx, ny, sum + map[ny][nx]);
        check[ny][nx] = 0;
    }
}
 
int main(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            check[i][j] = 1;
            dfs(1, j, i, map[i][j]);
            check[i][j] = 0;
            int x1, x2, x3, y1, y2, y3, d1, d2, d3;
            for (int d = 0; d < 4; d++)
            {
                d1 = d; d2 = d + 1; d3 = d + 2;
                if (d2 > 3) d2 -= 4;
                if (d3 > 3) d3 -= 4;
                x1 = j + dx[d1]; y1 = i + dy[d1]; x2 = j + dx[d2]; y2 = i + dy[d2]; x3 = j + dx[d3]; y3 = i + dy[d3];
                if (x1 < 0 || y1 < 0 || x1 >= M || y1 >= N || x2 < 0 || y2 < 0 || x2 >= M || y2 >= N || x3 < 0 || y3 < 0 || x3 >= M || y3 >= N) continue;
                if (map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3] > dab) dab = map[i][j] + map[y1][x1] + map[y2][x2] + map[y3][x3];
            }
        }
    cout << dab << endl;
    return 0;
}