[BOJ 14500] 테트로미노

14500번: 테트로미노

 

1. 문제 설명

2. 구현 아이디어 1 - 시간초과

한 좌표를 기준으로 테트로미노를 종이 위에 하나 놓는 모든 경우의 수는 해당 좌표를 기준으로 3칸 이동하는 모든 경우의 수와 동일하다.

그러므로 이중 반복문을 사용하여 모든 좌표에 대해 DFS+백트래킹으로 3칸을 이동했을 때 수들의 합을 구한 뒤 최댓값을 구하면 된다.

 

하지만 여기까지만 구현한다면 예제 입력 3에서 틀릴 것이다.

왜냐하면 T 모양 테트로미노는 3칸 이동하는 것으로 구현하는 것이 불가능하기 때문이다.

 

그러므로 DFS+백트래킹으로 T 모양을 제외한 4개의 테트로미노로 구할 수 있는 수들의 합의 최댓값을 구하고, 한번 더 이중 반복문을 순회하며 T 모양 테트로미노로 구할 수 있는 최댓값과 비교하여 최종 답을 구하였다.

#include <bits/stdc++.h>

using namespace std;

typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dfs(int x, int y, int cnt, int sum, vvi &board, vvb &visited, int ret) {
    // 종료 조건
    if (cnt == 3) {
        return max(ret, sum);
    }

    int n = board.size();
    int m = board[0].size();
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (visited[nx][ny]) continue;

        visited[nx][ny] = true;
        ret = dfs(nx, ny, cnt+1, sum+board[nx][ny], board, visited, ret);
        visited[nx][ny] = false;
    }

    return ret;
}

int tBlock(int sx, int sy, vvi &board) {
    vvi square = vvi(3, vector<int>(3, 0));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            square[i][j] = board[sx+i][sy+j];
        }
    }

    return max({square[0][0] + square[0][1] + square[0][2] + square[1][1],
                square[1][0] + square[1][1] + square[1][2] + square[0][1],
                square[1][0] + square[1][1] + square[1][2] + square[2][1],
                square[2][0] + square[2][1] + square[2][2] + square[1][1],
                square[0][0] + square[1][0] + square[2][0] + square[1][1],
                square[0][1] + square[1][1] + square[2][1] + square[1][0],
                square[0][1] + square[1][1] + square[2][1] + square[1][2],
                square[0][2] + square[1][2] + square[2][2] + square[1][1]});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    vvi board = vvi(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> board[i][j];
        }
    }

    int ret = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // DFS + 백트래킹
            vvb visited = vvb(n, vector<bool>(m, false));
            visited[i][j] = true;
            int sum = dfs(i, j, 0, board[i][j], board, visited, 0);
            ret = max(ret, sum);
        }
    }

    for (int i = 0; i <= n-3; ++i) {
        for (int j = 0; j <= m-3; ++j) {
            ret = max(ret, tBlock(i, j, board));
        }
    }

    cout << ret << "\n";

    return 0;
}

 

 

처음에는 tBlock 함수 때문에 시간 초과가 발생했다고 생각하여 ret과 tBlock을 비교하는 이중 for문을 주석 처리해보았는데, 그럼에도 시간 초과가 발생한걸 보아 백트래킹에서 시간 초과가 발생한 것이다.

 

2. 구현 아이디어 2 - 맞았습니다 !!

dfs 함수에서 백트래킹을 완료한 후에는 시작 좌표를 제외한 visited 배열의 모든 원소가 false로 초기화가 된다. 그러므로, dfs 함수 밖에서 visited 처리를 해준 (i, j)만 false로 바꿔준다면 모든 좌표마다 visited 배열을 선언해줄 필요가 없다.

 

아래와 같이 코드를 수정하여 시간 초과를 해결하고 문제를 맞출 수 있었다.

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        // DFS + 백트래킹
        visited[i][j] = true;
        int sum = dfs(i, j, 0, board[i][j], board, visited, 0);
        ret = max(ret, sum);
        visited[i][j] = false;
    }
}

 

---

 

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

를 보면 백트래킹이 효율적이고 노가다로 인한 실수를 방지할 수 있는 풀이지만, 모든 블럭의 모양을 정의해두고 완전 탐색을 하는 것이 2배 가량 빠르다고 한다.