[DFS] 테트로미노 (백준 14500번)

숫자가 예쁜 문제다, 14500번.

 

 

일단 문제에 대해서 간단한 해설을 쓰자면, 이건 무조건 dfs로밖에 풀 수 없는 문제다.

간단히 문제를 요약하건대,

아무 숫자가 적혀져 있는 2차원 배열이 주어질 때,

그 배열 위에 테트로미노 (이상, 위에 나와 있는 5가지 도형, 그리고 그 도형의 회전과 대칭)를 올려서

테트로미노 위에 적혀져 있는 숫자들의 합이 가장 큰 것을 구하는 문제이다.

 

고로 테트로미노가 4칸을 합쳐서 만든 도형이라는 특성 상,

dfs든 bfs든 4칸이 되는 순간, 합을 반환하고 종료시켜야 하는데,

bfs는 한 지점으로부터 상하좌우로 이동하기 때문에, 만들어진 도형이 반드시 인접할 거란 보장이 없다.

그에 반해 dfs는 한붓그리기와 같은 형태라서 안심하고 사용할 수 있다.

 

다만

 

dfs의 경우에는 ㅏ ㅓ ㅗ ㅜ 의 형태를 구할 수 없다. (말했다시피 한붓 그리기 형태만 가능하므로.)

(한글의 우수성이 놀랍지 아니한가. 그냥 헛소리다.)

 

그래서 ㅏ ㅓ ㅗ ㅜ의 형태만을 구해주는 함수를 만들어서 그 합도 따로 구해줘야 하는데,

이 부분은 솔직히 방법이 없다!

경우의 수 4가지를 모두 따져가야 하는데, 어느 한 점을 기준으로 하여금,

그 점으로부터 ㅏ ㅓ ㅗ ㅜ 중 성립이 가능한 형태에 대해 합을 구하면 된다.

당연 2차원 배열 밖으로 벗어나는 경우가 발생하기 때문에, 그 경우에는 탐색을 종료시켜야 한다.

 

#define _CRT_SECURE_NO_WARNINGS    
#include <iostream>
#include <algorithm>
using namespace std;
 
int map[502][502];
bool visited[502][502];
 
int xMove[4] = { 0,0,-1,1 };
int yMove[4] = { 1,-1,0,0 };
 
int n, m;
int sum, maximum = -1;
int fuckSum;
int counted;
 
void init(void)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            visited[i][j] = false;
}
 
// bfs로 하게 되면 서로 떨어진 블록을 하나로 인식할 가능성이 있어서 논외,
// dfs로 하게 되면 한붓 그리기 형태기 때문에 fuckSum을 고려하지 않는다.
// 다른 사람은 어떻게 했나 보려고 했다가, 내가 fuckSum을 고려하지 않았단 것을 알았다.
 
// 이 함수를 만든 사람이 fuck 이라는 이름으로 함수를 만들었기 때문에,
// 경외심을 가지고 그 사람의 함수 명, 변수 명을 그대로 가지고 왔다.
void fuck(int y, int x)
{
    fuckSum = 0;
    // ㅗ 모양 / 현재 좌표는 ㅡ 모양에서 중심
    if (2 <= y && y <= n && 2 <= x && x < m)
        fuckSum = max(fuckSum, map[y][x] + map[y - 1][x] + map[y][x - 1] + map[y][x + 1]);
    // ㅏ 모양 / 현재 좌표는 ㅣ 모양에서 중심
    if (2 <= y && y < n && 1 <= x && x <= m)
        fuckSum = max(fuckSum, map[y][x] + map[y][x + 1] + map[y - 1][x] + map[y + 1][x]);
    // ㅜ 모양 
    if (1 <= y && y < n && 2 <= x && x < m)
        fuckSum = max(fuckSum, map[y][x] + map[y + 1][x] + map[y][x - 1] + map[y][x + 1]);
    // ㅓ 모양
    if (2 <= y && y < n && 2 <= x && x <= m)
        fuckSum = max(fuckSum, map[y][x] + map[y][x - 1] + map[y - 1][x] + map[y + 1][x]);
    maximum = max(maximum, fuckSum);
}
 
void dfs(int y, int x)
{
    visited[y][x] = 1;
    sum += map[y][x];
    counted++;
    
    if (counted == 4)
    {
        if (maximum < sum)
        {
            maximum = sum;
            return;
        }
        else
            return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nextY = y + yMove[i];
        int nextX = x + xMove[i];
 
        if (nextY > 0 && nextY <= n && nextX > 0 && nextX <= m
            && visited[nextY][nextX] == 0)
        {
            visited[nextY][nextX] = 1;
            dfs(nextY, nextX);
 
            sum -= map[nextY][nextX];
            counted--;
            visited[nextY][nextX] = 0;
 
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d",&map[i][j]);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            counted = 0;
            dfs(i, j);
//            sum -= map[i][j];
            sum = 0;
            visited[i][j] = 0;
 
            // maximum
            fuck(i, j);
        }
 
    printf("%d", maximum);
}

 

놀랍지 아니한가.

Fuck이라는 함수를 만든 사람을 보고, 그 발상에 경이감을 감출 수가 없었다.

코드가 아름다워서 경이로웠던 적은 많지만 함수의 명칭에 경이로웠던 적이 있던가...