[백준] 14500번 테트로미노

문제

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

풀이

테트로미노의 종류는 총 5가지이지만 Dfs를 통해 탐색을 할 수 있는 경우는 4가지다.

ㅗ모양은 Dfs로 탐색을 할 수 없기에 따로 탐색하는 함수를 만들었다.

이 경우에는 인접한 칸을 모두 검사했을 경우 그 중에 가장 작은 값을 빼서 최대값을 구하는 방법으로 구현했다.

처음에 접근을 테트로미노마다 다른 Dfs를 만들어서 각각 다른 회전을 써야되나 싶어서 어려워한 문제다.

문제를 좀 더 쉽게 풀 수 있는 방법부터 생각해보는 게 좋을 것 같다.

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_SIZE 501
#define MIN_INF -987654321
#define MAX_INF 987654321

int ans = MIN_INF;
int n, m;
int paper[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

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

void Dfs(int x, int y,int curr_cnt, int curr_sum)
{
    // 4개의 칸으로 완성되면 종료
    if (curr_cnt == 4)
    {
        ans = max(ans, curr_sum);
        return;
    }

    visited[x][y] = true;

    for (int k = 0; k < 4; k++)
    {
        int next_x = x + dx[k], next_y = y + dy[k];

        if (!IsRange(next_x, next_y)) continue;

        if (visited[next_x][next_y] == false)
        {
            Dfs(next_x, next_y, curr_cnt + 1, curr_sum + paper[x][y]);
        }
    }

    visited[x][y] = false;
}

// ㅗ 모양 체크
void CheckException(int x, int y)
{
    int min = MAX_INF;
    int sum = paper[x][y];
    int cnt = 0;

    for (int k = 0; k < 4; k++)
    {
        int next_x = x + dx[k], next_y = y + dy[k];

        if (!IsRange(next_x,next_y)) continue;

        cnt++;
        sum += paper[next_x][next_y];
        if (min > paper[next_x][next_y])
            min = paper[next_x][next_y];
    }

    if (cnt == 4)
        sum -= min;

    ans = max(ans, sum);

}

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

    cin >> n >> m;

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            Dfs(i, j, 0, 0);
            CheckException(i, j);
        }
    }

    cout << ans << "\n";

    return 0;
}