[C++] 백준 14500번: 테트로미노

🔗 문제

14500번: 테트로미노

14500번: 테트로미노

 

🖍 풀이

모든 위치에서 탐색을 한다.

• 내 위치를 포함한 주변 위치를 총 4개를 모은다. 이게 테트로미노다.

DFS로 4개를 만들든 BFS로 만들든 아무튼 인접한 공간 4개를 모으면 된다.

어떤 모양으로 모였나 디버깅하면 알겠지만 ㅗ, ㅜ, ㅏ, ㅓ 모양으로 방문하는게 어렵다는걸 알게 될 거다.

 

BFS로 하면 만들 수 있는 줄 알았는데 안되길래 따로 oh()라는 함수로 방문해 줬다. (저주받은 작명)

BFS로 풀면 508ms이고 DFS로 풀면 100ms의 시간으로 꽤 차이가 많이 나서 BFS 코드는 버렸다 🙂

 

💾  소스

#include <iostream>

const int MAX = 500 + 1;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int N, M, answer = 0;
int map[MAX][MAX];
bool visited[MAX][MAX] = {false, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=M)
        return false;
    return true;
}

void show()
{
    printf(" - show - \\n");
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            std::cout << visited[i][j];
        }
        std::cout << '\\n';
    }

}

void oh(const int i, const int j)  // ㅏ ㅓ ㅗ ㅜ
{
    int sum = map[i][j];

    if(isValid(i+1, j) && isValid(i-1, j))
    {
        if(isValid(i, j+1))
        {
            answer = std::max(answer, map[i+1][j] + map[i-1][j] + map[i][j+1] + sum);
        }
        
        if(isValid(i, j-1))
        {
            answer = std::max(answer, map[i+1][j] + map[i-1][j] + map[i][j-1] + sum);
        }
    }
    
    if(isValid(i, j+1) && isValid(i, j-1))
    {
        if(isValid(i+1, j))
        {
            answer = std::max(answer, map[i][j+1] + map[i][j-1] + map[i+1][j] + sum);
        }
        
        if(isValid(i-1, j))
        {
            answer = std::max(answer, map[i][j+1] + map[i][j-1] + map[i-1][j] + sum);
        }
    }
}

void solve(int i, int j, int depth, int sum)
{
    if(depth == 4)
    {
        //show();
        answer = (answer > sum ? answer : sum);
        return;
    }
    

    for(int d=0; d<4; ++d)
    {
        int x = i + dx[d];
        int y = j + dy[d];
        
        if(visited[x][y] || !isValid(x, y))
            continue;
        
        visited[x][y] = true;
        solve(x, y, depth + 1, sum + map[x][y]);
        visited[x][y] = false;
    }
    
}

int main()
{
    std::cin >> N >> M;
    
    for(int i=0; i<N; ++i)
        for(int j=0; j<M; ++j)
            std::cin >> map[i][j];
    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            visited[i][j] = true;
            oh(i, j);
            solve(i, j, 1, map[i][j]);
            visited[i][j] = false;
        }
    }
    
    std::cout << answer;
    
    return 0;
}