[백준 14500번] 테트로미노

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

14500번: 테트로미노

풀이) 

구현문제일거라 생각했는데 간단한 dfs문제였다. 4개였기 때문에 직전에 왔던 좌표만 안 밟으면 되기에 visited배열은 따로 만들지 않고, 직전에 넘어왔던 위치만 기억해두고 해당 위치만 돌지않는 방법으로 재귀를 돌렸다.

여기서 간과했던 사실은 테트리스에서 'ㅜ' 모양은 dfs로 해결되지않기에 나머지 모양을 다 돌려보고 마지막으로 해당 부분만 다시 한번 확인해주어서 해결할 수 있었다.

#include <iostream>
using namespace std;

int N, M, maxV = -1, tmp;
int map[501][501] = {0,};
int dir_x[4] = {0, 0, 1, -1};
int dir_y[4] = {1, -1, 0, 0};

void dfs(int x, int y, int tx, int ty, int count, int total)
{
    if (count == 3)
    {
        maxV = max(maxV, total);
        return ;
    }
    
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir_x[i];
        int ny = y + dir_y[i];

        if (nx < 1 || nx > N || ny < 1 || ny > M || (tx == nx && ty == ny))
            continue ;
        
        dfs(nx, ny, x, y, count + 1, total + map[nx][ny]);
    }
}

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

    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> map[i][j];
    
    for (int i = 1; i <= N; i++)
       for (int j = 1; j <= M; j++)
        {
           dfs(i, j, 0, 0, 0, map[i][j]);
           
           if (i + dir_x[0] >= 1 && i + dir_x[0] <= N && j + dir_y[0] >= 1 &&  j + dir_y[0] <= M &&
                i + dir_x[1] >= 1 && i + dir_x[1] <= N && j + dir_y[1] >= 1 &&  j + dir_y[1] <= M &&
                i + dir_x[2] >= 1 && i + dir_x[2] <= N && j + dir_y[2] >= 1 &&  j + dir_y[2] <= M)
               tmp = map[i][j] + map[i + dir_x[0]][j + dir_y[0]] + map[i + dir_x[1]][j + dir_y[1]] + map[i + dir_x[2]][j + dir_y[2]];
           maxV = max(maxV, tmp);
           
           if (i + dir_x[0] >= 1 && i + dir_x[0] <= N && j + dir_y[0] >= 1 &&  j + dir_y[0] <=M &&
                i + dir_x[1] >= 1 && i + dir_x[1] <= N && j + dir_y[1] >= 1 &&  j + dir_y[1] <=M &&
                i + dir_x[3] >= 1 && i + dir_x[3] <= N && j + dir_y[3] >= 1 &&  j + dir_y[3] <=M)
               tmp = map[i][j] + map[i + dir_x[0]][j + dir_y[0]] + map[i + dir_x[1]][j + dir_y[1]] + map[i + dir_x[3]][j+dir_y[3]];
           maxV = max(maxV, tmp);
           
           if( i + dir_x[0] >= 1 && i + dir_x[0] <= N && j + dir_y[0] >= 1 &&  j + dir_y[0] <=M &&
                i + dir_x[3] >= 1 && i + dir_x[3] <= N && j + dir_y[3] >= 1 &&  j + dir_y[3] <=M &&
                i + dir_x[2] >= 1 && i + dir_x[2] <= N && j + dir_y[2] >= 1 &&  j + dir_y[2] <=M)
               tmp = map[i][j] + map[i + dir_x[0]][j + dir_y[0]] + map[i + dir_x[3]][j + dir_y[3]] + map[i + dir_x[2]][j + dir_y[2]];
           maxV = max(maxV, tmp);
           
           if( i + dir_x[3] >= 1 && i + dir_x[3] <= N && j + dir_y[3] >= 1 &&  j + dir_y[3] <=M &&
                i + dir_x[1] >= 1 && i + dir_x[1] <= N && j + dir_y[1] >= 1 &&  j + dir_y[1] <=M &&
                i + dir_x[2] >= 1 && i + dir_x[2] <= N && j + dir_y[2] >= 1 &&  j + dir_y[2] <=M)
               tmp = map[i][j] + map[i + dir_x[3]][j + dir_y[3]] + map[i + dir_x[1]][j + dir_y[1]] + map[i + dir_x[2]][j + dir_y[2]];
           maxV = max(maxV, tmp);
        }
    cout << maxV;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!