백준 14500번 테트로미노

문제 링크입니다: https://www.acmicpc.net/problem/14500

테트로미노를 회전이나 대칭을 시켜도 되기 때문에 'ㅗ' 모양을 빼고는 모두 DFS(Depth First Search)로 표현할 수 있습니다.

연구소 문제(http://jaimemin.tistory.com/601)처럼 모든 칸을 다 확인해야하기 때문에 visited[y][x]를 잘 이용해야 합니다.

'ㅗ' 모양은 DFS를 통해 표현할 수 없기 때문에 회전까지 고려하여 총 4가지 경우의 수를 모두 직접 계산해줘야 합니다.

따라서, 문제에서 요구하는 것은 DFS를 4번 했을 때의 합과 직접 계산한 4가지 경우의 수 중 최대를 출력하는 것이였습니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 500;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N, M;

int cell[MAX][MAX];

bool visited[MAX][MAX];

 

//전형적인 DFS

int DFS(int y, int x, int cnt)

{

        if (cnt == 4)

                 return cell[y][x];

       

        int sum = 0;

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && !visited[nextY][nextX])

                 {

                         visited[nextY][nextX] = true;

                         sum = max(sum, cell[y][x] + DFS(nextY, nextX, cnt + 1));

                         visited[nextY][nextX] = false; //꼭 처리해줘야한다

                 }

        }

        return sum;

}

 

//DFS로 판별할 수 없는 테트로미노

int middleFinger(int y, int x)

{

        int result = 0;

        //ㅗ (현재 좌표 ㅡ의 가운데)

        if (y >= 1 && x >= 1 && x < M - 1)

                 result = max(result, cell[y][x - 1] + cell[y][x] + cell[y - 1][x] + cell[y][x + 1]);

        //ㅏ (현재 좌표 ㅣ의 가운데)

        if (y >= 1 && y < N - 1 && x < M - 1)

                 result = max(result, cell[y - 1][x] + cell[y][x] + cell[y][x + 1] + cell[y + 1][x]);

        //ㅜ (현재 좌표 ㅡ의 가운데)

        if (y >= 0 && y < N - 1 && x < M - 1)

                 result = max(result, cell[y][x - 1] + cell[y][x] + cell[y + 1][x] + cell[y][x + 1]);

        //ㅓ (현재 좌표 ㅣ의 가운데)

        if (y >= 1 && y < N - 1 && x >= 1)

                 result = max(result, cell[y - 1][x] + cell[y][x] + cell[y][x - 1] + cell[y + 1][x]);

        return result;

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         cin >> cell[i][j];

 

        int result = 0;

        for(int i=0; i<N; i++)

                 for (int j = 0; j < M; j++)

                 {

                         visited[i][j] = true;

                         result = max(result, DFS(i, j, 1));

                         result = max(result, middleFinger(i, j));

                         visited[i][j] = false; //꼭 처리해줘야한다

                 }

 

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~