테트리미노 (백준 14500)

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

1️⃣ 풀이방법

이런 문제는 보통 이렇게 구현해야 할 것이 많으면, 공통된 규칙이 있다.
맨 마지막 모양을 제외한 나머지 구조들은 dfs를 통해 회전, 대칭이 다 가능하다. -> 각 구조들을 저장하고 rotate할 필요가 없다.
즉, bfs에서 어느 한 지점에서 회전할 수 있는 방향으로 한 번씩 이동했다면, dfs에서는 총 4칸을 걸쳐 쭉 한번에 칸을 갔다가(구조 모양 중 하나가 된다), 다시 돌아와서 다른 방향으로 한 칸을 가 또 다른 구조 하나를 만든다. 이런식으로 연속적으로 반복되면, 모든 구조를 다 맞춰볼 수 있다.
맨 마지막 모양은 따로 맞춰주면 답을 구할 수 있다.

2️⃣ Things to remember

• 이러한 도형 문제가 나오면, dfs와 같은 규칙이 있는지 아니면 단순히 x와 y의 규칙이 있는지 잘 살펴보자
• 방문확인과 움직이는 방향은 최대한 제약하지 말자. 생각지 못한 예외가 있을 수 있다(항상 그래왔음^^)

3️⃣ code

#include <bits/stdc++.h>
using namespace std;
int mx, x, y;
int board[501][501];
bool visited[501][501];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

void    last_case(int i, int j)
{
    if (i + 1 < x && j + 2 < y)
    {
        mx = max(mx, board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i + 1][j + 1]);
        mx = max(mx, board[i][j + 1] + board[i + 1][j] + board[i + 1][j + 1] + board[i + 1][j + 2]);
    }
    if (i + 2 < x && j + 1 < y)
    {
        mx = max(mx, board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 1][j + 1]);
        mx = max(mx, board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1] + board[i + 2][j + 1]);
    }
}

void    dfs(int xx, int yy, int t, int sum)
{
    if (t == 3)
    {
        mx = max(mx, sum);
        return ;
    }
    for (int dir = 0; dir < 4; dir++)
    {
        int nx = xx + dx[dir];
        int ny = yy + dy[dir];
        if (nx < 0 || ny < 0 || nx >= x || ny >= y)
            continue;
        if (visited[nx][ny])
            continue;
        visited[nx][ny] = true;
        dfs(nx, ny, t + 1, sum + board[nx][ny]);
        visited[nx][ny] = false;
    }
}

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

    cin >> x >> y;
    for (int i = 0; i < x; i++)
        for (int j = 0; j < y; j++)
            cin >> board[i][j];

    for (int i = 0; i < x; i++)
    {
        for (int j = 0; j < y; j++)
        {
            visited[i][j] = true;
            dfs(i, j, 0, board[i][j]);
            visited[i][j] = false;
            last_case(i, j);
        }
    }
    cout << mx;
    return (0);
}