백준/골드
[백준 14500번] 테트로미노 (C++)
게임개발기원
2023. 3. 10. 02:38
문제링크 : https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pil pair <int, int>
int arr[500][500], visited[500][500];
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};
int N, M, result;
void lastshape(int y, int x)
{
if(y + 1 < N && x + 2 < M) // ㅗ
{
result = max(result, arr[y][x] + arr[y][x+1] + arr[y][x+2] + arr[y+1][x+1]);
}
if(y - 1 >= 0 && x + 2 < M) // ㅜ
{
result = max(result, arr[y][x] + arr[y][x+1] + arr[y][x+2] + arr[y-1][x+1]);
}
if(y + 2 < N && x + 1 < M) // ㅏ
{
result = max(result, arr[y][x] + arr[y+1][x] + arr[y+2][x] + arr[y+1][x+1]);
}
if(y + 2 < N && x - 1 >=0) // ㅓ
{
result = max(result, arr[y][x] + arr[y+1][x] + arr[y+2][x] + arr[y+1][x-1]);
}
}
void cal_dfs(int cnt, int sum, int y, int x) //깊이가 4인 도형들
{
if(cnt == 3)
{
result = max(result, sum);
return;
}
for(int i=0; i<4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = true;
cal_dfs(cnt + 1, sum + arr[ny][nx], ny, nx);
visited[ny][nx] = false; //방문 초기화
}
}
void cal_max(int y, int x)
{
lastshape(y, x);
visited[y][x] = true;
cal_dfs(0, arr[y][x], y, x);
visited[y][x] = false; //방문 초기화
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for(int i=0; i<N; i++)
{
for(int j=0; j<M; j++)
{
cin >> arr[i][j];
}
}
for(int i=0; i<N; i++)
{
for(int j=0; j<M; j++)
{
cal_max(i, j);
}
}
cout << result;
return 0;
}
ㅗ 모양 도형을 제외한 나머지 도형들은 전부 깊이가 4이다.
따라서 dfs를 통해서 최대 합을 구할 수 있다.
ㅗ 모양 도형의 경우 회전이 가능하기에 경우의 수가 ㅗ, ㅜ, ㅓ, ㅏ 이렇게 4가지이다.
이 4가지에 대해서만 따로 직접 각각의 위치를 더해줌으로써 최대 합을 구한다.
완전탐색을 통해 각 위치에 대해 탐색하므로, 한번의 계산과정을 통해 방문처리 해준 것은 다음 값이 탐색을 시작하는 것을 위하여 반드시 방문처리를 풀어줘야 한다.
ㅗ 모양 도형으로 계산하는 방법과 같이 나머지 도형도 dfs 없이 없이 저런 노가다로 가능은 하겠으나,, 너무 하드 코딩일 듯 하다.