[BOJ] C++ 14500: 테트로미노 - 백트래킹 심화 문제

14500번: 테트로미노

예제

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

ans : 19

---

문제 분석부터 해보자. 테트로미노라는 블록을 보드에 넣는데, 블록이 들어가는 칸의 합이 가장 크게 되는 숫자를 찾으면 된다. 테트로미노는 총 5 종류고, 가장 먼저 떠오르는 방법은 모든 테트로미노를 하나하나 끼워 넣는 방법이다. 보드의 크기가 2500이고 블록 단 한 개만 넣으면 되므로 모든 테트로미노를 다 끼워보는 방법으로 구현해도 될 것 같다.

 

여기서 문제가 되는게, 모든 테트로미노를 구하는 방법이다. 5종류의 블록을 방향 회전까지 고려하면 총 19개의 케이스가 나오는데, 이 모든 케이스를 다 좌표로 구현하는 방법이 가장 먼저 떠올랐다. 이 방법은 확실히 시간 안에 풀 수 있을 것 같지만 19개의 블록을 좌표화 시키면서 실수가 일어날 것 같아서 일단 다른 방법도 좀 생각해 봤다. 

 

다음 방법은 백트래킹을 이용한 길이 4의 길을 찾는 문제로 바꾸는 것이다. dfs 느낌으로 구현하면 될 것 같은데 문제는 ㅏ ㅓ ㅗ ㅜ 블럭이다. 이 블록들은 일단 정 안되면 좌표화시켜서 따로 체크한다고 치고 구현해 봤다.

void func(int x, int y, int cnt)
{
    // 현재 (x, y) 방문, cnt 길이까지의 길 다 찾은 상태
    if (cnt == 4)
    {
        ans = max(ans, tmp_sum);
        return;
    }
    for (int dir = 0; dir < 4; dir++)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
        if (visited[nx][ny])
            continue;
        //(nx, ny) 방문 처리
        tmp_sum += board[nx][ny];
        visited[nx][ny] = true;
        func(nx, ny, cnt + 1);
        tmp_sum -= board[nx][ny];
        visited[nx][ny] = 0;
    }
}

딱히 구현에 어려운 부분은 없고, tmp_sum을 이용해서 값을 계속 누적시켜 나가는 방식이 좀 좋았다. 처음부터 tmp_sum으로 누적합을 구하진 않았고 cnt와 같이 값을 넘겨주는 방식으로 구현했는데, 다른 사람의 코드를 보다 보니 최적화할 부분이 보여서 최적화했다. visited 배열을 썼다가 다시 복구시키는 것처럼 누적합도 이런 식으로 사용할 수 있었다.

 

이제 ㅏ 블록 시리즈를 처리해줘야 하는데 그림을 그리면서 좌표화 말고 방법이 있을지 생각해 봤다.

사진처럼 해결 방법을 찾았다. cnt == 3인 (x, y)의 이전칸에서 줄기를 뻗으면 된다는 건데, func 함수 호출이 끝나면 그 점을 방문한 상태로 두고 func를 호출했다. 코드로 보는 게 편할 것 같다. 

 

아마 처음부터 이 방법을 떠올리기 상당히 어려울 수 있는데, 실제 코테에서 만났다면 고민하지 말고 예외 케이스는 좌표화시켜서 처리하는 게 나을 것 같다. 이제 풀어봤으니 비슷한 백트래킹이 나오면 응용할 수 있을 것이다.

/** 시뮬레이션 14500 테트로미노 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m, ans = 0, tmp_sum = 0;
int board[510][510];
bool visited[510][510];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void func(int x, int y, int cnt)
{
    // 현재 (x, y) 방문, cnt 길이까지의 길 다 찾은 상태
    if (cnt == 4)
    {
        ans = max(ans, tmp_sum);
        return;
    }
    for (int dir = 0; dir < 4; dir++)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
            continue;
        if (visited[nx][ny])
            continue;
        //(nx, ny) 방문 처리
        tmp_sum += board[nx][ny];
        visited[nx][ny] = true;
        func(nx, ny, cnt + 1);
        // 주의!! ㅏ ㅓ ㅗ ㅜ 모양 처리를 위해 길이 3의 길까지 찾은 후
        // nx, ny의 방문 한 채로 x, y에서 다시 다음 길을 찾으면서 해결
        if (cnt == 2)
            func(x, y, cnt + 1);
        tmp_sum -= board[nx][ny];
        visited[nx][ny] = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            tmp_sum = board[i][j];
            visited[i][j] = true;
            func(i, j, 1);
            visited[i][j] = false;
        }

    cout << ans << '\n';
}