[14500] 테트로미노

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

이번 문제는 테트로미노이다.

주어진 다섯 가지 도형 중 딱 하나만을 사용해 종이에 올려 놓았을 때

가장 큰 값을 구하는 문제이다.

예전에 한 번 풀고 이번 기회에 다시 풀어서 풀이가 두 가지가 있다.

매우 비슷하지만 약간 차이가 있으니 둘 다 소개하겠다.

사실 똑같은 방법이긴 하다.

먼저 첫 번째 방법은

도형을 잘 살펴보면 알겠지만 T 모양의 도형을 제외하고 나머지 도형들은 한 붓그리기 처럼

처음 점에서 마지막 점 까지 쭉 연결할 수 있다.

이걸 이용해 상 하 좌 우 를 숫자로 세 자리 순열을 만든다. ex) 111 ~ 444

처음 점과 이 세 자리 순열을 이용해 도형을 만든다.

이때 주의해야할 점은 아래 -> 위, 왼 쪽 -> 오른 쪽와 같이 반대 방향으로 가면 도형이 만들어지지 않는다.

이런 순열은 버리고 각 도형의 최대 값을 찾으면 된다.

그 후 T 모양 도형은 따로 구해 준 후 이들 중 최대 값을 구하면 된다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, arr[550][550], maxi;
int disc[5];
int dx[5] = { 0, 0, 1, 0, -1 };
int dy[5] = { 0, 1, 0, -1, 0 };
 
int tx[4] = { 0, 0, 0, 1 };
int ty[4] = { 0, 1, 2, 1 };
int mx[4] = { 1, -1, 1, -1 };
int my[4] = { 1, 1, -1, -1 };
 
void tShape(int x, int y) {
    int nx, ny, ret;
    for (int i = 0; i < 4; i++) {
        ret = arr[x][y];
        for (int j = 1; j <= 3; j++) {
            nx = x + tx[j] * mx[i];
            ny = y + ty[j] * my[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
            ret += arr[nx][ny];
        }
        maxi = max(maxi, ret);
        ret = arr[x][y];
        for (int j = 1; j <= 3; j++) {
            nx = x + ty[j] * my[i];
            ny = y + tx[j] * mx[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
            ret += arr[nx][ny];
        }
        maxi = max(maxi, ret);
    }
}
void func(int x, int y, int num, int last) {
    if (num == 4) {
        int nx, ny;
        nx = x; ny = y;
        int ret = arr[nx][ny];
        
        for (int i = 1; i <= 3; i++) {
            nx += dx[disc[i]];
            ny += dy[disc[i]];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
            ret += arr[nx][ny];
        }
 
        maxi = max(maxi, ret);
        
        return;
    }
    for (int i = 1; i <= 4; i++) {
        if (abs(i - last) == 2) continue;
        disc[num] = i;
        func(x, y, num + 1, i);
        disc[num] = 0;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    maxi = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            func(i, j, 1, -10);
            tShape(i, j);
        }
    }
    printf("%d\n", maxi);
 
    return 0;
}

두 번째 방법은 다 똑같은데 위에서 말한 순열을 조금만 다르게 생각해서 풀었다.

생각해보면 한 붓 그리기처럼 그릴 수 있다는 말은 그냥 그 점에서 길이가 4인 DFS를 말한다.

그러므로 현재 점에서 DFS를 수행하고 길이가 4가 된 순간 최대 값을 갱신해주면 된다.

T도형은 마찬가지로 따로 구해주었다.

끝.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, maxi;
int arr[555][555];
bool visit[555][555];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int shapeX[4][4] = {{0, 1, 2, 1}, {0, 1, 2, 1}, {0, 0, 0, -1}, {0, 0, 0, 1}};
int shapeY[4][4] = {{0, 0, 0, 1}, {0, 0, 0, -1}, {0, 1, 2, 1}, {0, 1, 2, 1}};
void dfs(int x, int y, int cnt, int sum){
    if(cnt == 4){
        maxi = max(maxi, sum);
        return ;
    }
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=m || visit[nx][ny]) continue;
        visit[nx][ny] = 1;
        dfs(nx, ny, cnt+1, sum+arr[nx][ny]);
        visit[nx][ny] = 0;
    }
}
 
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    maxi = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            visit[i][j] = 1;
            dfs(i, j, 1, arr[i][j]);
            visit[i][j] = 0;
 
            for(int p=0; p<4; p++){
                int sum = 0;
                for(int q=0; q<4; q++){
                    int nx = i+shapeX[p][q];
                    int ny = j+shapeY[p][q];
                    if(nx<0 || nx>=n || ny<0 || ny>=m) 
                        break;
                    sum += arr[nx][ny];
                }
                maxi = max(maxi, sum);
            }
        }
    }
 
    printf("%d\n", maxi);
 
 
    return 0;
}