백준 14500 테트로미노 C++ [컴공과고씨]

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

14500번: 테트로미노

 

문제 정리

바둑판이 주어지고 각 칸에는 숫자가 써있음.

여기에 4칸으로 이루어진 도형 5개 주어짐.

바둑판에 도형 한 개를 놓아서 놓아진 칸의 숫자 합이 최대가 되도록 만들어라.

 

문제 해결 방법

이 문제를 해결하는 방법은 대표적으로 DFS를 사용하는 방법이 있습니다.

제가 처음 푼 방법은 DFS를 쓰지 않고 풀었습니다.

하지만 DFS를 쓰는 방법에 대해 설명하고 제가 푼 방법을 설명하도록 하겠습니다.

전체 코드는 제가 처음 푼 방법과 dfs로 푼 방법 둘다 작성해 두었습니다.

 

DFS

도형들을 보시면 ㅗ 모양 빼고는 깊이가 4인 dfs로 탐색을 하면 도형을 만들 수 있다. 

즉, 칸 마다 dfs를 돌려서 깊이가 4까지 탐색을 해서 각 칸의 합을 구해줍니다.

그후에 ㅗ모양을 따로 빼서 구해주는 방식으로 해주면 됩니다.

 

다른 방법

근데 저는 어차피 ㅗ모양을 회전시키면서 따로 또 구해주어야 하니 처음부터 도형의 경우를 나누었습니다.

제 방식은 ㅡㅡㅡㅡ 모양은 쉽게 구할 수 있기 때문에 따로 구해주고

위 처럼 6칸짜리 직사각형에서 2칸을 빼서 도형을 만들어 주는 식으로 구현했습니다. 

이렇게 하면 직사각형에서 위 5가지 경우 도형을 빼주면 일자를 제외한 도형을 만들 수 있습니다.

주의해야 할 것은 

이런 모양이 나올때는 제외 시켜주면 됩니다.

 

전체코드 (처음 푼 코드)

#include <iostream>
#include <queue>
using namespace std;
int result = 0;
int cnt = 0;
int map[502][502];
int dx1[] = {1, 2, 2, 0, -2};
int dy1[] = {0, 1, 0, 1, 1};
int dx2[] = {1, 1, -1, 0, 0};
int dy2[] = {0, 2, 2, 2, 1};
 
bool IsAns(int a){ 
    return result < a;
}
bool IsMin(int a, int b){
    return a < b;
}
int main(){
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m;j++){
 
            if(j+3 < m){ // 가로 일자 도형 
                int wids = 0;
                for (int k = j; k <= j+3; k++){
                    wids += map[i][k];
                }
                if(IsAns(wids)){
                    result = wids;
                }
            }
 
            if(i+3 < n){ // 세로 일자 도형
                int wids = 0;
                for (int k = i; k <= i+3; k++){
                    wids += map[k][j];
                }
                if(IsAns(wids)){
                    result = wids;
                }
            }
 
            if(i+1 < n && j+2 < m){ // 2행 3열 직사각형
                int sum = 0; // 직사각형 전체 합.
                int temp = 98765432; // 2칸 빼줄 숫자 합.
                // 직사각형에서 2칸씩 빼주는 과정
                for (int k = i; k <= i + 1;k++){ 
                    for (int q = j; q <= j + 2;q++){
                        sum += map[k][q];
                        for (int t = 0; t < 5;t++){
                            int temp2;
                            int ny = k + dy1[t];
                            int nx = q + dx1[t];
                            if(t == 3 && nx == j+1) // 제외할 모양
                                continue;
                            if(ny >= i && ny <= i+1 && nx >=j && nx <= j+2){
                                temp2 = map[k][q] + map[ny][nx];
                                //빼주는 도형의 합이 최소가 되어야함.
                                if(IsMin(temp2, temp))
                                    temp = temp2; 
                            }
                        }
                    }
                }
                sum -= temp;
                // 정답 가능 여부 체크
                if(IsAns(sum)){
                    result = sum;
                }
            }
 
            if(i+2 < n && j+1 < m){ //3행 2열 직사각형 위와 똑같은 과정
                int sum = 0;
                int temp = 98765432;
                for (int k = i; k <= i + 2;k++){
                    for (int q = j; q <= j + 1;q++){
                        sum += map[k][q];
                        for (int t = 0; t < 5;t++){
                            int temp2;
                            int ny = k + dy2[t];
                            int nx = q + dx2[t];
                            if(t == 0 && ny == i+1)
                                continue;
                            if(ny >= i && ny <= i+2 && nx >=j && nx <= j+1){
                                temp2 = map[k][q] + map[ny][nx];
                                if(IsMin(temp2, temp))
                                    temp = temp2;
                            }
                        }
                    }
                }
                sum -= temp;
                if(IsAns(sum)){
                    result = sum;
                }
            }
        }
    }
 
    cout << result << endl;
    return 0;
}

 

 

DFS

#include <iostream>
using namespace std;
int map[502][502];
bool visit[502][502];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;
int result;
void dfs(int a,int b, int cnt, int sum){
    if(cnt == 3){
        if(sum > result){
            result = sum;   
        }
        return;
    }
    for (int i = 0; i < 4;i++){
        int nx = a + dx[i];
        int ny = b + dy[i];
 
        if(nx >= 0 && nx < m && ny >=0 && ny < n && !visit[ny][nx]){
            visit[ny][nx] = true;
            dfs(nx, ny, cnt + 1, sum + map[ny][nx]);
            visit[ny][nx] = false;
        }
    }
}
 
int main(){
    cin >> n >> m;
 
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m;j++){
            cin >> map[i][j];
        }
    }
 
    for (int i = 0; i < n;i++){
        for (int j = 0; j < m; j++){
            visit[i][j] = true;
            dfs(j, i, 0, map[i][j]);
            visit[i][j] = false;
            int sum = 0;
 
            // ㅗ 모양들
            if(i-1 >=0 && j+2<m){ 
                sum = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i-1][j + 1];
                if(sum > result)
                    result = sum;
                sum = 0;
            }
 
            if(i+1 <n && j+2<m){
                sum = map[i][j] + map[i][j + 1] + map[i][j + 2] + map[i+1][j + 1];
                if(sum > result)
                    result = sum;
                sum = 0;                
            }
 
            if(i+2 <n && j+1<m){
                sum = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j + 1];
                if(sum > result)
                    result = sum;
                sum = 0;
            }
 
            if(i+1 <n && i-1>=0 && j+1 < m){
                sum = map[i][j] + map[i - 1][j+1] + map[i][j+1] + map[i+1][j +1];
                if(sum > result)
                    result = sum;
                sum = 0;
            }
                        
        }
    }
    cout << result << endl;
    return 0;
}