[백준14500] 테트로미노 C++

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

예제 입력 1

5 5

1 2 3 4 5

5 4 3 2 1

2 3 4 5 6

6 5 4 3 2

1 2 1 2 1

풀이

'ㅗ' 모양 때문에 귀찮아진 문제!

 

dfs 함수는 현재 시작 좌표에서 만들 수 있는 테트로미노들을 모두 찾아서 최댓값을 구해준다

 

'ㅗ' 모양은 블럭들을 순서대로 나열해서 만들 수 없는 모양이라서 따로 작업이 필요했다.

is_near함수를 만들어서 해결

#include <iostream>
#include <vector>
using namespace std;
 
struct P{
    int row, col;
};
 
int N, M;
int Paper[501][501];
bool visited[501][501];
int result = 0;
 
void input(){
    cin >> N >> M;
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            cin >> Paper[r][c];
            visited[r][c] = false;
        }
    }
}
 
vector<P> tblock;
bool temp_visited[501][501];
 
// dfs가 돌아가면서 어떤 좌표에 어떤 테트로미노가 놓이는지 보여줌
void show_block(){
    int Map[501][501];
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            Map[i][j] = 1;
        }
    }
    for(int i = 0; i < tblock.size(); i++){
        Map[tblock[i].row][tblock[i].col] = 0;
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cout << Map[i][j] << " ";
        }
        cout << endl;
    }
}
 
inline bool is_near(int row, int col){
    for(int i = 0; i < tblock.size(); i++){
        int a = abs(tblock[i].row - row);
        int b = abs(tblock[i].col - col);
        // 새로운 블럭의 좌표가 기존 블럭의 좌표들과 하나라도 붙어있으면 true 리턴 
        if((a == 1 && b == 0) || (a == 0 && b == 1)) return true;
    }
    return false;
}
 
void dfs(int row, int col, int used_block){
    // 여러 과정을 거쳐 만들어진 블럭의 개수가 4개이면 블럭들의 좌표에 있는 값들을 더해서
    // 지금까지의 결과값과 비교해 큰 값으로 갱신한다
    // 그리고 마지막에 들어왔던 블럭을 삭제하고 다른 자리의 마지막 블럭을 탐색해본다
    if(used_block == 4){
        tblock.push_back({row, col});
        int temp_result = 0;
        for(int i = 0; i < 4; i++){
//            cout << tblock[i].row << " " << tblock[i].col << endl;
            temp_result += Paper[tblock[i].row][tblock[i].col];
        }
        
        result = max(result, temp_result);
//        cout << endl;
//        show_block();
        tblock.pop_back();
        return;
    }
    
    temp_visited[row][col] = true;
    tblock.push_back({row, col});
//    show_block();
//    cout << endl;
    // r과 c모두 -1 부터 1까지라서 현재 블럭의 대각선 좌표까지도 접근 가능하다 -> 'ㅗ'를 만들기 위함
    for(int r = -1; r <= 1; r++){
        for(int c = -1; c <= 1; c++){
            // 다음 방문할 좌표가 Paper 안에 있지 않거나, dfs를 돌면서 방문한 좌표거나, 지금까지 탐색한 좌표중 하나이면 좌표를 탐색하지 않는다
            if(row+r < 0 || col+c < 0 || row+r >= N || col+c >= M || visited[row+r][col+c] || temp_visited[row+r][col+c]) continue;
            // 현재 만들어진 블럭들과 다음 방문할 좌표가 붙어있으면 다음 방문할 좌표의 블럭을 지금까지 만들어진 블럭에 추가할 수 있다
            if(is_near(row+r, col+c)){
                dfs(row+r, col+c, used_block+1);
            }
        }
    }
    // 현재 좌표를 사용해서 만들 수 있는 블럭을 다 만들었으면
    // 마지막에 들어간 블럭을 빼고 다른 블럭을 넣어서 탐색해 본다
    tblock.pop_back();
    temp_visited[row][col] = false;
}
 
void solve(){
    
    for(int r = 0; r < N; r++){
        for(int c = 0; c < M; c++){
            visited[r][c] = true;
            dfs(r, c, 1);
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
    cout << result;
    
    return 0;
}
 

-- 내 풀이가 속도 측면에서 매우 좋은 풀이는 아니고 중복으로 찾는 경우도 있는걸 발견했다..

   원인을 찾으면 코드를 고쳐서 포스팅을 수정하겠다.

for(int r = -1; r <= 1; r++){
        for(int c = -1; c <= 1; c++){

풀고나서 다른 블로그를 봤는데 대부분 'ㅗ', 'ㅏ', 'ㅓ', 'ㅜ' 모양들을 따로 예외로 정해놓고 푸신것 같았다.

내 풀이에 비해서는 확실히 깔끔했다. 다양한 사람들이 선택한 풀이는 이유가 있었다!

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, M, result;
int MAP[501][501];
bool visited[501][501];
 
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
 
void input(){
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++){
            cin >> MAP[i][j];
        }
    }
}
 
void dfs(int r, int c, int sum, int cnt){
    visited[r][c] = true;
    
    if(cnt == 3){
        result = max(result, sum);
        return;
    }
    
    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        
        if(nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
        if(visited[nr][nc]) continue;
        
        dfs(nr, nc, sum + MAP[nr][nc], cnt+1);
        visited[nr][nc] = false;
    }
}
 
// ㅗ ㅜ ㅏ ㅓ 를 따로 찾아주는 방법
// ㅗ
inline void Shape1(int x, int y){
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x - 1][y + 1];
    result = max(result, Tmp_Sum);
}
 
// ㅜ
inline void Shape2(int x, int y){
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x][y + 1] + MAP[x][y + 2] + MAP[x + 1][y + 1];
    result = max(result, Tmp_Sum);
}
 
// ㅏ
inline void Shape3(int x, int y){
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x + 1][y] + MAP[x + 2][y] + MAP[x + 1][y + 1];
    result = max(result, Tmp_Sum);
}
 
// ㅓ
inline void Shape4(int x, int y){
    int Tmp_Sum = 0;
    Tmp_Sum = MAP[x][y] + MAP[x - 1][y + 1] + MAP[x][y + 1] + MAP[x + 1][y + 1];
    result = max(result, Tmp_Sum);
} 
 
void solve(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            memset(visited, false, sizeof(visited));
            dfs(i, j, MAP[i][j], 0);
            // ㅗ ㅜ ㅏ ㅓ 찾기
            if(i - 1 >= 0 && j + 2 < M) Shape1(i, j);   // ㅗ
            if(i + 1 <  N && j + 2 < M) Shape2(i, j);   // ㅜ
            if(i + 2 <  N && j + 1 < M) Shape3(i, j);   // ㅏ
            if(i - 1 >= 0 && i + 1 < N && j + 1 < M) Shape4(i, j);   // ㅓ
        }
    }
    cout << result;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
    
    return 0;
}