백준 - 테트로미노 알고리즘 전략

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

14500번: 테트로미노

 

new 연산자 비용은 비싸다.

 

미천한 실력을 쌓는 와중에 며칠간 고민하게 만들었던 문제 

테트리미노 (테트로미노) I, O, L, J, S, Z, T

처음 접근 방법은 DFS(Depth First Search); 깊이 우선 탐색을 사용한 탐색 방법 이였다. 미로찾기 할 때 주로 BFS를 사용했고 Queue로 구현 했어서, DFS는 Queue 대신 Stack만 사용하면 될 것이라고 생각하고 시작을 했는데, 4번째 칸을 어떻게 구분할지 고민을 하다가 스택은 사용하지 않고, 깊이 4에서 return 하는 재귀함수로 구현하면 되겠다 라는 생각을 했다.

부분집합(Subset)을 구할때, 봤던 알고리즘 중에 그렇게 구현하는 방식을 봤던 것 같다. 

 

테트리미노의 최대값을 구하는 문제라서

그래서 dfs() 메서드를 구현할때 아래와 같이 구현 하였다. 

int dfs(int sum, int[][] area, boolean[][] visited, int x, int y, int num)

(return int 로 처음에 작성하였는데 문제가 있어 이후에 void 로 수정)

 

누적 값 sum, 배열 area, 배열의 방문여부 visited, 누적된 마지막 row.col 인 x,y, 누적된 칸 num 

으로 구성하였다. 

 

미로찾기 로직 처럼 상(-1, 0), 하(1, 0), 좌(0, -1) 우(0, 1) 를 x y 에 더한 값을 재귀로 탐색하는 로직으로 작성하였다. 

모든 모양 테트리미노를 각각 좌표를 순환하는 것이 시간은 가장 짧게 걸릴 것 같은데, I, O 테트리미노는 간단할 것 같으나

나머지 L, J, S, Z, T의 경우까지 하면 코드 라인 자체가 굉장히 길어질 것 같았다. 알고리즘 이라기보다는 구현이라고 생각하고 풀어도 될 것으로 보이나 그렇게 풀고 싶진 않았다.

T 모양 테트리미노 제외하고는 깊이 탐색으로 가능하고, [0,0] ~ [N-1, M-1] 까지 전체를 시작으로 돈다고 할때 상(-1,0) 방향 진행은 제외해도 완전탐색 되겠다 라고 생각 되었다. (3/4 로 탐색범위 감소)

T 테트리미노 탐색로직을 별도로 구현하려고 생각하다 보니, 상하좌우를 그냥 전부 탐색하고 두번째 위치에서 세번째 네번째 두군데를 고르면 된다고 생각을 해서 아래와 같이 코드를 변경 하였다.

visited[nextX][nextY] = true;
if(num == 2) dfs(sum + area[nextX][nextY], area, visited, x, y, num + 1);
dfs(sum + area[nextX][nextY], area, visited, nextX, nextY, num + 1);
visited[nextX][nextY] = false;

두 번째 라인이 T 테트리미노를 탐색하는 코드

이렇게 구현하고 예시 코드로 테스트를 진행하는데, 결과가 바로 나오지 않았다.

전체 탐색 시간이 너무 많이 걸려서 라고 생각을 했고, 

전체 위치를 다 탐색하는 것이 문제라고 생각했다. 

그래서 Main 클래스의 변수로 전체 값 중 큰 값(maxOfBlock)을 저장하였고, DFS 중 남은 블럭 * maxOfBlock 값이 지금까지 탐색한 테트리미노 최대값(max) 보다 작으면 탐색안하고 반환하도록 하였다.

이 과정을 하기 위해 int로 테트리미노 값을 반환하게 했던 기존 로직에서 void 반환으로 하고 max를 전역변수로 선언하여 num == 4 일 때, max 값을 갱신하도록 하였다.

private static void dfs(int sum, int[][] area, boolean[][] visited, int x, int y, int num) {
    if(num == 4) {
        if(sum > max) max = sum;
    }
    if ((4 - num) * maxOfBlock + sum <= max) {
        return;
    }
    for (int[] step : moving) {
        int nextX = x + step[0];
        int nextY = y + step[1];
        if(canMove(nextX, nextY) && !visited[nextX][nextY]) {
            visited[nextX][nextY] = true;
            if(num == 2) dfs(sum + area[nextX][nextY], area, visited, x, y, num + 1);
            dfs(sum + area[nextX][nextY], area, visited, nextX, nextY, num + 1);
            visited[nextX][nextY] = false;
        }
    }
}

변경한 dfs() 전체 코드

 이렇게 추가/변경하고 실행하여도, 시간초과가 계속 발생했다. 

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        findMaxTetrimino(i, j, area);
    }
}

......

private static void findMaxTetrimino(int i, int j, int[][] area) {
        boolean[][] visited = new boolean[N][M];
        visited[i][j] = true;
        dfs(area[i][j], area, visited, i, j, 1);
        visited[i][j] = false;
    }

아래와 같이 구현된 상태였는데, visited[][] 배열을 좌표마다 생성하고 제거하는 시간이 오래걸린것으로 확인 되었다.

visited[][] 를 전역변수로 변경하였다.  맨 위에 표시 했지만, new 생성하는 비용이 비싸다는걸 직접 실감 할 수 있었다.

 

아래는 완성된 전체 코드이다.