테트로미노

문제: 테트로미노

구조 분석

해당 문제는 지금까지 열심히 풀었던 전형적인 보드판 위의 구현문제이다. 이는 brute force를 이용해 매 칸을 탐색하며 해당 칸을 시점으로 하는 테트리스 블록의 점수 중 최대값을 구하는 문제로 4칸짜리 테트리스 블록을 구현하기 위해 dfs를 이용했다.

DFS를 이용한 이유는 max depth가 4이고 optimal 여부와 관련이 없고 또한 backtracking을 이용해야 하기 때문이다. BFS의 경우 queue를 사용하여 백트래킹이 불가능하다.

풀이 방법

해당 문제의 경우 처음에 완벽히 구현했다고 생각했는데 시간초과가 생겼다. 이 때문에 매우 당황했는데 시간초과가 난 지점은 visited 여부를 체크하고 매번 init 시켜주는 데에서 일어났다. DFS를 재귀적으로 호출하는데 매 호출마다 map 전부를 일일히 확인하면 시간복잡도가 map 탐색크기만큼 필요이상으로 증가하기 때문이다. 따라서 재귀적으로 호출하는 dfs 구조에서 호출전에 visited를 true로 변경하고 호출이 끝나고 리턴 이후에 visited를 false로 다시 변경해주는 식으로 수정했다.

이를 수정한 뒤에도 틀렸는데 이 이유는 ㅗ,ㅏ,ㅓ,ㅜ와 같은 코너케이스를 놓쳤기 때문이다. 이를 해결해주기 위해서 각 모양마다 체크해주는 함수를 따로 만들어 해결했다.

코드

#include <stdio.h>
#include <iostream>
#include <stack>
#define MAX(a,b) (a>b?a:b)
using namespace std;

int n, m;
int ans = 0;
int cost = 0;
int map[500][500] = {0,};
int visited[500][500] = {0,};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

void dfs(int x, int y, int cnt) {
    if (cnt == 4) {
        ans = MAX(ans, cost);
        return;
    }
    for (int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (visited[nx][ny] == 1) continue;
        visited[x][y] = 1;
        cost += map[nx][ny];
        dfs(nx,ny,cnt+1);
        visited[x][y] = 0;
        cost -= map[nx][ny];
    }
}

void shape1(int x, int y) {
    int cost = 0;
    cost = map[x][y] + map[x][y+1] + map[x][y+2] + map[x-1][y+1];
    ans = MAX(ans, cost);
}

void shape2(int x, int y) {
    int cost = 0;
    cost = map[x][y] + map[x][y+1] + map[x][y+2] + map[x+1][y+1];
    ans = MAX(ans, cost);
}

void shape3(int x, int y) {
    int cost = 0;
    cost = map[x][y] + map[x+1][y] + map[x+2][y] + map[x+1][y+1];
    ans = MAX(ans, cost);
}

void shape4(int x, int y) {
    int cost = 0;
    cost = map[x][y] + map[x-1][y+1] + map[x][y+1] + map[x+1][y+1];
    ans = MAX(ans, cost);
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            visited[i][j] = 1;
            cost = map[i][j];
            dfs(i,j,1);
            visited[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 <n && i-1 >= 0 && j+1 < m) shape4(i,j);
        }
    }
    cout << ans << "\n";
    return 0;
}

정리

해당 문제의 구조는 이제 익숙해졌다. 그러나 이런 문제는 매 번 강조하지만 코너케이스를 유의해야한다.