문제 링크 : https://www.acmicpc.net/problem/14500
문제 풀이
이 문제는 NxM 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다. 여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.
N,M ≤ 500 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 O(MN)인데, 정확히는 백트랙킹 할 때 최대 4^4 개의 가짓수가 있어서 256MN만큼의 연산이 필요하다.
먼저 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;
}
'정보 > 백준 문제풀이' 카테고리의 다른 글
백준 28325번 호숫가의 개미굴 C++ (0) | 2024.05.25 |
---|---|
백준 28218번 격자 게임(2023 KOI 중등부 2번) C++(게임 이론) (0) | 2024.05.11 |
백준 1005번 ACM Craft C++ (0) | 2024.04.21 |
백준 16891번 탄성충돌 C++ (물리) (0) | 2024.03.24 |
백준 30928번 Yokohama Phenomena C++ (1) | 2024.03.23 |