백준 14500번 테트로미노 C++

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

문제 풀이

 이 문제는 NxM 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다. 

 

  N,M ≤ 500 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 O(MN)인데, 정확히는 백트랙킹 할 때 최대 4^4 개의 가짓수가 있어서 16MN만큼의 연산이 필요하다.

 

 먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.

void BT(int x, int y, int depth, int k)
{
    if(depth == 4)
    {
        num = max(num,k);
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!(nx>=0&&ny>=0&&nx<N&&ny<M&&!visited[nx][ny])) continue;
        visited[nx][ny] = true;
        BT(nx,ny, depth+1, k + graph[nx][ny]);
        visited[nx][ny] = false;
    }
}

 테트로미노이므로 깊이가 4가 되는 경우가 종료 조건이고, 이때 숫자의 합 k를 num이라는 변수와 비교 해주었다. 

 깊이가 아직 4가 안되었다면 dfs와 똑같이 인접한 칸들을 재귀적으로 탐색해주었다.

 

 근데 이렇게만 해서 코드를 짜보면 틀렸다고 나온다. 왜냐하면 dfs를 통해서만 탐색하면 아래와 같은 모양의 테트로미노는 사용할 수 없게 된다.

이 테트로미노를 사용하려면 가운데 칸을 기준으로 bfs 비슷하게 탐색해주면 된다. 이를 구현한 코드는 아래와 같다.

void BFS(int x, int y)
{
    vector<pair<int,int>> neighbor;
    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx>=0&&ny>=0&&nx<N&&ny<M) neighbor.push_back({nx,ny});
    }
    if(neighbor.size()<3) return;
    for(int i=0;i<neighbor.size();i++) num += graph[neighbor[i].first][neighbor[i].second];
    if(neighbor.size()==3) return;
    int mn = 9999;
    for(int i=0;i<4;i++)
    {
        mn = min(mn,graph[neighbor[i].first][neighbor[i].second]);
    }
    num -= mn;
}

 이웃한 칸이 2개 이하인 칸은 탐색을 하지 않는다. 이웃한 칸이 3개이면 그 모든 칸을 포함시키면 되고, 4개이면 적힌 숫자가 최소인 칸만 포함시키지 않으면 된다. 이건 한 칸 마다 시간복잡도가 O(1)이고, 모든 칸에 대해 했을 때에는 O(MN)이므로 이것도 TLE가 나지 않는다.

 

시행 착오

 1) BT함수 종료조건을 depth == 5일 때로 했었다.

 2) 처음에는 BT로 dfs만 해서 핑크 테트로미노를 고려하지 못했다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,graph[500][500],num=0;
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
bool visited[500][500];
void BFS(int x, int y)
{
    vector<pair<int,int>> neighbor;
    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx>=0&&ny>=0&&nx<N&&ny<M) neighbor.push_back({nx,ny});
    }
    if(neighbor.size()<3) return;
    for(int i=0;i<neighbor.size();i++) num += graph[neighbor[i].first][neighbor[i].second];
    if(neighbor.size()==3) return;
    int mn = 9999;
    for(int i=0;i<4;i++)
    {
        mn = min(mn,graph[neighbor[i].first][neighbor[i].second]);
    }
    num -= mn;
}
void BT(int x, int y, int depth, int k)
{
    if(depth == 4)
    {
        num = max(num,k);
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!(nx>=0&&ny>=0&&nx<N&&ny<M&&!visited[nx][ny])) continue;
        visited[nx][ny] = true;
        BT(nx,ny, depth+1, k + graph[nx][ny]);
        visited[nx][ny] = false;
    }
}
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>N>>M;
    for(int i=0;i<N;i++)for(int j=0;j<M;j++)cin>>graph[i][j];
    int max_num = 0;
    for(int i=0;i<N;i++)for(int j=0;j<M;j++){
        visited[i][j] = true;
        BT(i,j,1,graph[i][j]);
        max_num = max(max_num,num);
        num = 0;
        visited[i][j] = false;
    }
    for(int i=0;i<N;i++)for(int j=0;j<M;j++){
        num=graph[i][j];
        BFS(i,j);
        max_num = max(max_num,num);
        num = 0;
    }
    cout<<max_num;
}