백준 14500 - 테트로미노 (C++)

 

그림처럼 5종류의 테트로미노가 있다.

이 테트로미노의 모양에 맞게 배열에서 최대값을 탐색하면 된다.

 

 

이런 이차원 배열이 있다고 해보자.

 위처럼, 빨간색으로 ㅗ 모양으로 배열을 탐색할 수도 있고, 파란색처럼 ㄴ모양으로 탐색할 수도 있다.

노란색처럼 ㅁ모양으로 탐색할 수도 있다.

 

이렇게, 여러 모양에 대해 이차원 배열을 탐색하면서 4개 숫자의 합을 구하고, 그 중 최대값을 구하면 된다.

 

문제 풀이

이 4가지 도형에 대해선 그냥 DFS를 돌며 4칸을 탐색하면 된다.

한 지점에 대해, 이동할 수 있는 4칸에 대해 모두 DFS돌면 위와 같은 모든 도형에 대한 경우의 수를 탐색할 수 있다.

이런 식으로, 특정 좌표를 기준으로 4칸만큼 DFS를 하게 되면 결국 테트로미노 도형과 동일한 형태를 띄게 된다.

 

하지만, 한가지 예외인 도형이 있다.

 

이 모양의 도형은 DFS로 탐색할 수가 없다.

그렇기 때문에 이 도형에 대해서는 예외로 따로 최대값을 구해주었다.

 

즉, 이 문제는

1. 주위의 4칸으로 DFS를 하며 구한 최대값 

2. 보라색 도형의 모양으로 탐색한 최대값

 

두 경우에 대해 최대값을 모두 탐색한 뒤, 둘 중 더 큰 값을 출력하면 되는 문제이다.

 

 

풀이 코드

int Height = 0;
int Width = 0;

int Max = 0;

std::vector<std::vector<int>> Board;
std::vector<std::pair<int, int>> Dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

 

먼저 위와 같이 변수와 자료구조를 선언하였다.

 

Height 는 입력되는 배열의 높이이고, Width는 입력되는 배열의 길이이다.

Max는 답으로 출력하기 위한 최대값을 저장하는 변수이다.

 

Board는 입력되는 숫자를 저장할 배열이고, Dir은 DFS에서 4방향을 탐색하기 위해 만들어놓은 벡터이다.

 

std::cin >> Height >> Width;

Board.resize(Height, std::vector<int>(Width, 0));

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        std::cin >> Board[i][j];
    }
}

 

이후, 입력을 위와 같이 받았다.

 

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        DFS(j, i, -1, -1, 0, 1);
        GetMaxAnother(j, i);
    }
}

 

그리고, 모든 좌표에 대해 4칸까지 DFS를 하며 최대값을 갱신해주고, 예외인 ㅗ 모양의 도형에 대해서도 최대값을 갱신해주었다.

 

DFS함수 내부를 보자.

void DFS(int _X, int _Y, int _PrevX, int _PrevY, int _Sum, int _Depth)
{
    if (_Depth == 4)
    {
      Max = std::max(Max, _Sum + Board[_Y][_X]);
      return;
    }

    for (int i = 0; i < 4; i++)
    {
        int NextY = _Y + Dir[i].first;
        int NextX = _X + Dir[i].second;

        if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
        {
            continue;
        }

        if (_PrevX == NextX && _PrevY == NextY)
        {
            continue;
        }

        DFS(NextX, NextY, _X, _Y, _Sum + Board[_Y][_X], _Depth + 1);
    }
}

 

_X, _Y는 현재 좌표, _PrevX , _PrevY 는 이전 좌표, _Sum은 지나온 좌표에 적힌 숫자들의 합, _Depth는 현재 몇칸까지 탐색했는가 이다.

 

이 문제는 최대 4칸까지의 합만을 요구하기 떄문에 _Depth가 4가 되는 순간 최대값을 갱신하고 재귀함수를 종료하였다.

_PrevX와 _PrevY는 지나온 길을 다시 돌아가지 않기 위한 방문체크용이다.

 

배열을 따로 선언해도 되지만, 함수의 인자를 활용하는 편이 더 편하다고 생각하여 위와 같이 설계하였다.

또한, 배열을 만들지 않음으로써 메모리를 절약할 수도 있다.

 

이후, DFS를 돌며 상하좌우 4방향에 대해 나아가며 탐색하였다.

 

void GetMaxAnother(int _X, int _Y)
{
    if (_Y + 2 < Height)
    {
        int Sum = Board[_Y][_X] + Board[_Y + 1][_X] + Board[_Y + 2][_X];

        if (_X - 1 >= 0)
        {
            Max = std::max(Max, Sum + Board[_Y + 1][_X - 1]);
        }

        if (_X + 1 < Width)
        {
            Max = std::max(Max, Sum + Board[_Y + 1][_X + 1]);
        }
    }

    if (_X + 2 < Width)
    {
        int Sum = Board[_Y][_X] + Board[_Y][_X + 1] + Board[_Y][_X + 2];

        if (_Y - 1 >= 0)
        {
            Max = std::max(Max, Sum + Board[_Y - 1][_X + 1]);
        }

        if (_Y + 1 < Height)
        {
            Max = std::max(Max, Sum + Board[_Y + 1][_X + 1]);
        }
    }
}

 

이 함수는 ㅗ 모양의 도형에 대한 함수이다.

 

 

이렇게 1자 모양으로 3개의 숫자의 합을 구한 뒤, 빨간색 도형에 해당하는 좌표의 값을 더해주어

ㅗ 모양과 ㅜ모양에 대한 합을 탐색하였다.

 

 

이렇게 세로 방향으로도 진행하여 ㅓ 모양과 ㅏ 모양에 대해서도 합을 탐색하였다.

 

std::cout << Max;

return 0;

 

마지막으로 Max를 출력해주면 끝이다.

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
   std::ios::sync_with_stdio(false);
   std::cin.tie(nullptr);
   std::cout.tie(nullptr);
}

int Height = 0;
int Width = 0;

int Max = 0;

std::vector<std::vector<int>> Board;
std::vector<std::pair<int, int>> Dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void DFS(int _X, int _Y, int _PrevX, int _PrevY, int _Sum, int _Depth)
{
    if (_Depth == 4)
    {
        Max = std::max(Max, _Sum + Board[_Y][_X]);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int NextY = _Y + Dir[i].first;
        int NextX = _X + Dir[i].second;

        if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
        {
            continue;
        }

        if (_PrevX == NextX && _PrevY == NextY)
        {
            continue;
        }

        DFS(NextX, NextY, _X, _Y, _Sum + Board[_Y][_X], _Depth + 1);
    }
}

void GetMaxAnother(int _X, int _Y)
{
    if (_Y + 2 < Height)
    {
        int Sum = Board[_Y][_X] + Board[_Y + 1][_X] + Board[_Y + 2][_X];

        if (_X - 1 >= 0)
        {
            Max = std::max(Max, Sum + Board[_Y + 1][_X - 1]);
        }

        if (_X + 1 < Width)
        {
            Max = std::max(Max, Sum + Board[_Y + 1][_X + 1]);
        }
    }

    if (_X + 2 < Width)
    {
    	int Sum = Board[_Y][_X] + Board[_Y][_X + 1] + Board[_Y][_X + 2];

    	if (_Y - 1 >= 0)
    	{
    	    Max = std::max(Max, Sum + Board[_Y - 1][_X + 1]);
    	}

    	if (_Y + 1 < Height)
    	{
    	    Max = std::max(Max, Sum + Board[_Y + 1][_X + 1]);
    	}
    }
}

int main()
{
    Init();

    std::cin >> Height >> Width;

    Board.resize(Height, std::vector<int>(Width, 0));
    
    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            DFS(j, i, -1, -1, 0, 1);
            GetMaxAnother(j, i);
        }
    }

    std::cout << Max;

    return 0;
}