폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
단순하게 깊이4짜리 DFS로 접근했다.
문제는 t자 모양이였다. 파고들어가서 경로탐색하는 특성상 t자를 찾을수없어서 함수를 따로만들었다.
t자 처리함수
//T자 모양 블록 처리방안
int TShape(int curX, int curY)
{
int sum = 0;
sum += box[curX][curY];
int maxWay = 0;
//t자가 만들어질수 잇는 네 방식중 제일 큰값 구하는 부분
for (int i = 0; i < 4; i++)
{
int tmpSum = 0;
//i부터 i+2까지 세 좌표값 더하는 부분
for (int j = i; j < i+3; j++)
{
int idx = j % 4;
int nextX = curX + dirX[idx];
int nextY = curY + dirY[idx];
//가지치기
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
continue;
tmpSum += box[nextX][nextY];
}
//제일 값이 큰 경로로 가야함
maxWay = max(tmpSum, maxWay);
}
sum += maxWay;
return sum;
}
t자 모양은 상하좌우 네방향중 한방향만 빼놓으면 되므로
i에 대해 i, i+1 i+2 이 세가지 인덱스를 4로 % 연산하면 쉽게 구할수 있다
#include <string>
#include <vector>
#include<queue>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int dirX[4] = { 0,0,-1,1 };
int dirY[4] = { -1,1,0,0 };
int box[502][502];
bool visited[502][502];
int N,M;
int DFS(int curX,int curY,int curLevel)
{
int sum = 0;
if (curLevel == 4) return 0;
visited[curX][curY] = true;
sum += box[curX][curY];
int maxWay = 0;
for (int i = 0; i < 4; i++)
{
int nextX = curX + dirX[i];
int nextY = curY + dirY[i];
//가지치기
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
continue;
if (visited[nextX][nextY]) continue;
//제일 값이 큰 경로로 가야함
maxWay= max(maxWay,DFS(nextX, nextY, curLevel + 1));
}
sum += maxWay;
//다시방문할수도 있으니 false
visited[curX][curY] = false;
return sum;
}
//T자 모양 블록 처리방안
int TShape(int curX, int curY)
{
int sum = 0;
sum += box[curX][curY];
int maxWay = 0;
//t자가 만들어질수 잇는 네 방식중 제일 큰값 구하는 부분
for (int i = 0; i < 4; i++)
{
int tmpSum = 0;
//i부터 i+2까지 세 좌표값 더하는 부분
for (int j = i; j < i+3; j++)
{
int idx = j % 4;
int nextX = curX + dirX[idx];
int nextY = curY + dirY[idx];
//가지치기
if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
continue;
tmpSum += box[nextX][nextY];
}
//제일 값이 큰 경로로 가야함
maxWay = max(tmpSum, maxWay);
}
sum += maxWay;
return sum;
}
int main()
{
cin >> N >> M ;
int maxNum = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> box[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
int tmpResult = DFS(i, j, 0);
int tmpResult2 = TShape(i, j);
tmpResult = max(tmpResult,tmpResult2 );
maxNum = tmpResult > maxNum ? tmpResult : maxNum;
}
}
cout << maxNum;
}
시간 복잡도에 대해 생각해보면
dfs함수에선 각 깊이마다 4방향 탐색하고, 깊이는 최대 4이므로
시간복잡도는 4^3이다.
tshape함수에서는 4*3
전체 격자 N*M에 대해 처리해야하므로
(4^3 + 4*3 ) * N * M = O(N*M) 에 해당한다