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

문제링크 : https://noj.am/14500

1. 모든 경우의 수를 시뮬레이션하여 풀기

테트로미노가 나올 수 있는 모든 상황을 시뮬레이션해서 문제를 푸는 방법이다.

문제에서 조건을 살펴보면

N*M은 최대 500*500 = 250,000

테트로미노가 나올 수 있는 모양의 가지 수 = 19가지

250,000 * 19 = 4,750,000번 이므로 1억번을 초과하지 않는다.

무식하게 한 좌표를 기준으로 19번의 테트로미노의 상태 모두를 탐색하는 방법으로 푸는게 시간복잡도 면에서는 가장 효율적이다.

다만, 이 방법으로 풀 경우 모든 경우, 숫자를 한개라도 틀리게 적었을 경우 실수하기가 매우 쉽다.

// BOJ_14500 테트로미노
#include <iostream>
#include <vector>
 
using namespace std;
 
int dx[][4] = {{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 1, 1}, {0, 1, 2, 2},
               {1, 0, 0, 0}, {0, 0, 1, 2}, {1, 1, 1, 0}, {2, 2, 1, 0},
               {0, 0, 0, 1}, {2, 1, 0, 0}, {0, 1, 1, 1}, {0, 1, 1, 2},
               {1, 1, 0, 0}, {2, 1, 1, 0}, {0, 0, 1, 1}, {1, 1, 1, 0},
               {1, 0, 1, 2}, {0, 0, 0, 1}, {0, 1, 2, 1}};
 
int dy[][4] = {{0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 0, 1}, {0, 0, 0, 1},
               {0, 0, 1, 2}, {0, 1, 1, 1}, {0, 1, 2, 2}, {0, 1, 1, 1},
               {0, 1, 2, 2}, {0, 0, 0, 1}, {0, 0, 1, 2}, {0, 0, 1, 1},
               {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 1, 2, 1},
               {0, 1, 1, 1}, {0, 1, 2, 1}, {0, 0, 0, 1}};
 
int N, M;
vector<vector<int> > arr;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
int search(int x, int y) {
    int maxNum = 0;
    for (int i = 0; i < 19; i++) {
        int sum = 0;
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            // 범위를 벗어날 경우
            if (nx < 1 || ny < 1 || nx > N || ny > M)
                break;
            sum += arr[nx][ny];
        }
        maxNum = max(maxNum, sum);
    }
    return maxNum;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    cin >> N >> M;
    arr = vector<vector<int> >(N + 1, vector<int>(M + 1));
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> arr[i][j];
 
    int result = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            result = max(result, search(i, j));
 
    cout << result;
 
    return 0;
}

2. 백트래킹으로 문제 풀기

한 좌표를 중심으로 상/하/좌/우로 가지치기를 연속 3번 하다보면 테트로미노가 나올 수 있는 경우라는 것을 알 수 있다.

이러한 단서를 바탕으로 백트래킹으로 문제를 풀이하면 된다.

250,000 * 4 * 3 * 3 = 9,000,000번 (2회째부터 3회씩인 이유는 전 단계의 지점이 방문체크가 되었기 때문에)

다만, ㅗ 모양의 경우는 백트래킹으로는 절대로 나올 수 없기 때문에 별도로 예외 케이스를 계산해서 처리해야 한다.

+ 형태를 구해서 상,하,좌,우로 한개씩만 빼줄 경우 ㅓ ㅜ ㅏ ㅗ의 형태가 나온다.

각 좌표마다 O(1) 만큼의 시간 복잡도가 추가되므로 9,250,000번 탐색하게 된다.

시간복잡도 면에선 방법1과 비교했을땐 비효율적이지만 실수할 경우는 절대 없을 것 같다.

// BOJ_14500 테트로미노
#include <iostream>
#include <vector>
 
using namespace std;
 
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
 
int N, M;
int result = 0;
vector<vector<int> > arr;
vector<vector<bool> > visited;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
// 백트래킹
void search(int x, int y, int cnt, int sum) {
    // 테트로미노를 4번 더했을 경우 return
    if(cnt >= 4) {
        result = max(result, sum);
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > N || ny > M || visited[nx][ny])
            continue;
        visited[nx][ny] = true;
        search(nx, ny, cnt + 1, sum + arr[nx][ny]);
        visited[nx][ny] = false;
    }
}
 
// ㅗ 모양 탐색
void searchFxxk(int x, int y){
    int sum = arr[x][y];
    int cnt = 1;
    
    // + 모양 만들기
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > N || ny > M)
            continue;
        sum += arr[nx][ny];
        cnt++;
    }
    // cnt가 4이면 ㅓ ㅜ ㅏ ㅗ 중 하나임
    if(cnt == 4){
        result = max(result, sum);
        return;
    }
    // cnt가 4 이하면 제대로된 모양이 아님
    if(cnt < 4) return;
 
    // + 모양에서 상,하,좌,우 하나씩만 빼주면 ㅓ ㅜ ㅏ ㅗ가 나옴
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > N || ny > M)
            continue;
        result = max(result, sum - arr[nx][ny]);
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    cin >> N >> M;
    arr = vector<vector<int> >(N + 1, vector<int>(M + 1));
    visited = vector<vector<bool> >(N + 1, vector<bool>(M + 1, false));
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> arr[i][j];
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            // 백트래킹 탐색
            visited[i][j] = true;
            search(i, j, 1, arr[i][j]);
            visited[i][j] = false;
            // ㅗ모양 탐색
            searchFxxk(i, j);
        }
    }
 
    cout << result;
 
    return 0;
}

아래는 방법1, 위는 방법2로 풀었을 때, 걸린 시간이다. 약 2배 가량의 시간이 차이나는 것을 알 수 있다.