[BOJ] 14500 테트로미노

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

14500번: 테트로미노

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

brute-force

 

---------------------------------------------------풀이----------------------------------------------------

 

모든 도형의 가능한 위치를 배열로 저장해두고 풀면 바로 풀리겠지만, 조금 더 범용성 있는 코드를 작성하고 싶었다.

(N사 공채에서 잘못푼걸 그때 깨달은게 한이 된듯...)

재귀함수로 dfs()를 사용해 4개를 만드는 방법이 가장 많이 사용하는 방법이다.

이 경우, 한 사각형의 위치에서 인접한 곳에 다음 사각형을 선택하는 방식이기에, ㅗ/ㅏ/ㅜ/ㅓ 모양의 도형은 예외처리가 필요하다.

이 예외처리 없이, 그러니까 4개가 아니라 그 이상의 도형이 되더라도 사용 가능한 방법을 찾고 싶어 이 방식을 고안했다.

 

하나의 row에서 임의의 k개를 선택하고,

그 아래 row에서 선택 가능한 남은 개수 중 임의의 m개를 선택해 위의 row에서 선택한 column 값과 일부가 겹치도록 선택,

그 아래 row에서 임의의 n개 선택해서 위의 row에서 선택한 column 값과 일부가 겹치도록 선택,

...

이렇게 도형을 모두 선택할 때까지 선택해 나가는 방식이다.

모두 선택했다면 그 때의 합을 ans와 비교해 ans를 업데이트 한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

#define BLOCK_SIZE 4

int N, M;
int map[501][501] = {0, };
int ans = 0;

// 현재 선택하려는 블록의 row, 선택해야하는 남은 블록 수 left_block,
// 위에서 선택된 column의 시작값 col_s, 종료값 col_e. 이 값과 아래 row의 col 값이 겹치는 부분이 있어야 함.
void make_block(int row, int left_block, int col_s, int col_e, int sum){
    // 네 개의 블록을 모두 선택했으면 종료.
    if(left_block == 0){
        if(ans < sum){
            ans = sum;
        }
        return;
    }
    // row가 최대이면 종료.
    if(row >= N){
        return;
    }
    
    // 시작 column의 위치 선택
    for(int col = 0; col < M; col++){
        int cur_sum = 0;
        // 1개~left_block개 까지 이 (row, col)을 시작으로 선택
        for(int i = 0; i < left_block; i++){
            // col+i의 위치가 초과되면 pass
            if(col + i >= M){
                break;
            }
            cur_sum += map[row][col+i];
            // 위의 col_s~col_e의 값과 겹치는 값이 없으면 pass
            if(col > col_e || col+i < col_s){
                continue;
            }// 합을 구하며 다음 row를 호출
            make_block(row+1, left_block-(i+1), col, col+i, cur_sum + sum);
        }
    }
}

void solution(){
    // 블록이 시작할 줄을 선택
    for(int i = 0; i < N; i++){
        // i번째 row에서 시작
        make_block(i, BLOCK_SIZE, 0, M-1, 0);
    }
}

// 테트로미노 = 정사각형 네 개 이어붙인 도형. 회전이나 대칭 가능
// 테트로미노 하나를 적절히 놓을 때 테트로미노가 놓인 칸에 쓰여 있는 수들의 합의 최대=?
int main(void){
    FASTIO;
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
        }
    }
    solution();
    cout << ans << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

block을 각 row마다 몇 개를 선택할지 골라서 넘겼는데, 계속 틀렸습니다가 떠서 

https://www.acmicpc.net/board/view/119217

글 읽기 - << 테케 공유 >>

이 글을 참고해 해결했다.

나 같은 경우의 문제는 make_block()함수 내에서

38~48번째 줄의 sum을 구하는 데 문제가 있었다.

cur_sum += map[row][col+i]를 통해 누적된 합을 구하고 있었는데,

그 부분을 "if(col > col_e || col+i  < col_s) continue;" 아래에 넣어둬서

만약, [k]를 선택된 숫자로 한다면,

0 [1] [1]

1   0   0 <- 현재 체크할 row

이 상황에서 1이 누적된 합에 더해지지 않는 문제가 발생하였다.