https://www.acmicpc.net/problem/14500
문제
> 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
1. 정사각형은 서로 겹치면 안 된다.
2. 도형은 모두 연결되어 있어야 한다.
3. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
> 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
> 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다.
> 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
> 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
> 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
접근
브루트포스와 DFS를 통해 주어진 각각의 좌표에서 가능한 모든 경우를 따져준다.
추가로 ㅗ,ㅜ,ㅓ,ㅏ모양은 DFS로 중간에 꺾일 수 없기 때문에 따로 빼서 검사한다.
총 4개의 블럭을 쓰기 때문에 DFS에서 재귀로 사방탐색을 하여 가능한 모든 경로를 따진다. 그러면 가능한 테트로미노의 회전, 대칭이 모두 따져진다.
따지면서 더한 결과를 서로 비교해서 최대를 찾아주면된다.
문제해결
> 테트로미노를 탐색하는 DFS를 만든다. 입력으로 행,열이 들어오고, 몇개의 정사각형이 이어졌는지를 나타내기위해 num을, 각 폴리오미노의 값을 더한 sum을 받는다.
> 테트로미노의 조건으로 4개의 정사각형이 만들어졌을 때를 위해 num이 4인지 검증하고 맞다면 현재 위치까지의 값을 다 더해 그동안 누적된 Max값과 비교해 갱신해준다.
> 4개가 아니라면 더 이어줘야하므로 사방탐색으로 다음 좌표인 nr,nc를 구해 범위 밖인지 검증하고 범위 내라면 재귀로 해당 좌표를 가지고 들어간다.
> 재귀로 들어가기전 방문처리를 해주고, 재귀가 4개를만족하던, 불가능한경로여서 깨지던 다시 돌아왔을 때, 방문처리를 다시 false로 해줘야 모든 경우를 따져줄 수 있다.
> 이제 DFS로 못하는 T모양을 따져준다. 입력으로 현 좌표의 행과 열을 가지고, 메소드 내부에서 이를 기준으로 ㅗ,ㅜ,ㅓ,ㅏ 모양을 봐야하므로 각각 상하좌우의 좌표를 구해준다.
> 조건을 나누어 모양별로 각각의 상하좌우 좌표가 범위내에 있다면 따져주어야 하므로 이를 검증하고 값을 구해 각각 Max와 비교해 최대값을 갱신해준다.
> 이제 main함수에서 폴리오미노판을 입력받고 모든 좌표를 DFS에 넣어 따져준다. DFS가 끝나고 나오면 그 좌표의 T모양도 따져야 하므로 ShapeT메소드도 호출해 구해준다.
> 최종적으로 Max에 있는 최대값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> paper;
vector<vector<bool>> visited;
int Max = 0;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
void DFS(int r, int c, int num, int sum)
{
if (num == 4)
{
sum += paper[r][c];
Max = max(Max, sum);
return;
}
for (int i = 0; i < 4; i++)
{
int nr = r + dir[i];
int nc = c + dic[i];
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= M) continue;
if (!visited[nr][nc])
{
visited[nr][nc] = true;
DFS(nr, nc, num + 1, sum + paper[r][c]);
visited[nr][nc] = false;
}
}
}
void ShapeT(int r, int c)
{
int upnr = r - 1;
int upnc = c;
int lnr = r;
int lnc = c - 1;
int rnr = r;
int rnc = c + 1;
int dnr = r + 1;
int dnc = c;
if (upnr >= 0 && lnc >= 0 && rnc < M)//ㅗ
{
int upT = paper[r][c] + paper[upnr][upnc] + paper[lnr][lnc] + paper[rnr][rnc];
Max = max(upT, Max);
}
if (upnr >= 0 && lnc >= 0 && dnr < N)//ㅓ
{
int leftT = paper[r][c] + paper[upnr][upnc] + paper[lnr][lnc] + paper[dnr][dnc];
Max = max(leftT, Max);
}
if (upnr >= 0 && rnc < M && dnr < N)//ㅏ
{
int rightT = paper[r][c] + paper[upnr][upnc] + paper[dnr][dnc] + paper[rnr][rnc];
Max = max(rightT, Max);
}
if (dnr < N && lnc >= 0 && rnc < M)//ㅜ
{
int downT = paper[r][c] + paper[dnr][dnc] + paper[lnr][lnc] + paper[rnr][rnc];
Max = max(downT, Max);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
paper.resize(N, vector<int>(M));
visited.assign(N, vector<bool>(M, false));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> paper[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
visited[i][j] = true;
DFS(i, j, 1, 0);
visited[i][j] = false;
ShapeT(i, j);
}
}
cout << Max << '\n';
}
후기
각 테트로미노에 대해 4개의 사각형중 어떤 사각형을 기준으로 잡을지, 가능한 경우를 전부 따져야 하는지 고민이 많았지만 어딜 기준으로 잡던 가능한 경우를 전부 따지다 보면 다 고려가 되는걸 알았다. 그래서 일단 다 따져보니 됐다.
