구현 ( DFS를 이용 )

백준 14500번 구현문제를 DFS를 이용해 Java로 풀어보았다.
첫 번째 시도에서는 분명 이건 아닌 것 같지만 마땅히 다른 풀이에 대한 확신이 없기에 개삽질을 끝까지 했고 주어진 예시도 모두 통과했지만 제출해보니 틀렸다. 예상했지만 개삽질을 한 코드를 오래도 붙잡고 있었기에 쌍욕이 나왔다.

---

내가 짠 개삽질 코드의 로직은 다음과 같다. 로직이라 하기에도 뭐하다. 그냥 노가다.
각 테르로미노를 회전 및 대칭시켰을 때 몇 가지 종류가 나오는지에 따라 그 모든 경우에 대해 다 값을 구해주고 최댓값을 갱신했다. 만약 특정 모양이 map 바깥으로 벗어나면 구하지 않고 그냥 넘겼다.

이렇게 모든 테트로미노에 대한 가능한 경우 수를 모두 세면 15가지다. 15가지 경우를 모두 각 좌표에 대해 검사하는 이중 for문 안에 넣어줬다. 정말 엿같다.
코드는 다음과 같다.

int max = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(i+3<N)   max = (max<map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j] ? map[i][j]+map[i+1][j]+map[i+2][j]+map[i+3][j] : max);
                if(j+3<M)   max = (max<map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3] ? map[i][j]+map[i][j+1]+map[i][j+2]+map[i][j+3] : max);

                if(i+1<N && j+1<M)  max = (max<map[i][j]+map[i+1][j]+map[i][j+1]+map[i+1][j+1] ? map[i][j]+map[i+1][j]+map[i][j+1]+map[i+1][j+1] : max);

                if(i+2<N && j+1<M) max = (max<map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1] ? map[i][j]+map[i+1][j]+map[i+2][j]+map[i+2][j+1] : max);
                if(i-1>=0 && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i][j+2]+map[i-1][j+2] ? map[i][j]+map[i][j+1]+map[i][j+2]+map[i-1][j+2] : max);
                if(i+2<N && j+1<M) max = (max<map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] ? map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+2][j+1] : max);
                if(i-1>=0 && j+2<M) max = (max<map[i][j]+map[i-1][j]+map[i-1][j+1]+map[i-1][j+2] ? map[i][j]+map[i-1][j]+map[i-1][j+1]+map[i-1][j+2] : max);

                if(i+2<N && j+1<M) max = (max<map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1] ? map[i][j]+map[i+1][j]+map[i+1][j+1]+map[i+2][j+1] : max);
                if(i-1>=0 && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i-1][j+1]+map[i-1][j+2] ? map[i][j]+map[i][j+1]+map[i-1][j+1]+map[i-1][j+2] : max);
                if(i-2>=0 && j+1<M) max = (max<map[i][j]+map[i-1][j]+map[i-1][j+1]+map[i-2][j+1] ? map[i][j]+map[i-1][j]+map[i-1][j+1]+map[i-2][j+1] : max);
                if(i+1<N && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2] ? map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i+1][j+2] : max);

                if(i+1<N && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] ? map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] : max);
                if(i-1>=0 && i+1<N && j+1<M) max = (max<map[i][j]+map[i-1][j]+map[i+1][j]+map[i][j+1] ? map[i][j]+map[i-1][j]+map[i+1][j]+map[i][j+1] : max);
                if(i-1>=0 && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i-1][j+1]+map[i][j+2] ? map[i][j]+map[i][j+1]+map[i-1][j+1]+map[i][j+2] : max);
                if(i-1>=0 && i+1<N && j+1<M) max = (max<map[i][j]+map[i-1][j+1]+map[i][j+1]+map[i+1][j+1] ? map[i][j]+map[i-1][j+1]+map[i][j+1]+map[i+1][j+1] : max);
            }
        }

오우쒯~
그리고 틀렸다 ㅆㅂ^^

---

DFS 를 이용하자

사실 처음에 딱 보자마자 깊이를 4로 한 DFS를 이용하면 되지 않을까 했지만, 모든 모양을 다 커버할 수 없을 것 같다는 생각에 그냥 15가지 경우를 다 구현했다.
그런데 다시 보니, 그냥 예외 경우는 따로 구해주면 되는 거지 15가지를 다 구현해버리는 ㅂㅅ짓을 열심히도 했다.

DFS를 이용해서 가능한 모든 경우는 ㅗ 모양을 제외하고는 모두 가능하기 때문에 ㅗ 모양만 따로 계산해주면 된다.

깊이가 4인 DFS

끝까지 들어가는 게 아니라 딱 4칸까지만 움직이고 값을 내야하기 때문에 parameter 로 몇 번째인지를 넣어줘서 끝 맺도록 해야 한다. 또 현재 합산 값은 얼마인지 알려주기 위해 sum을 parameter 로 넣어줘야 한다.
시작할 때는 sum을 해당 좌표의 값을 넣어주고, cnt값은 0으로 넣어주어 0,1,2,3 순서로 탐색해 3을 만나면 끝내주면 된다.
그럼 DFS 메소드 코드만 먼저 살펴보자.

static void dfs(int row, int col, int sum, int cnt){
        if(cnt==3){ // 3인 채로 넘어왔으면 이미 4번째 칸에 있는 것
            max = Math.max(max, sum);
            return;
        }

        for(int i=0; i<4; i++){
            int nRow = row + directionRow[i];
            int nCol = col + directionCol[i];

            if(nRow>=0 && nRow<N && nCol>=0 && nCol<M && !visited[nRow][nCol]){
                visited[nRow][nCol] = true;
                dfs(nRow, nCol, sum + map[nRow][nCol], cnt+1);
                visited[nRow][nCol] = false; // 다시 초기화!
            }
        }
    }

이 때 조심해야할 것은 visited 정보다. 기존 보편적인 DFS가 아니라 변형된 DFS기 때문에 방문 정보 값에 대한 처리를 조금 다르게 해줘야 한다. 한 텀을 마쳤으면 방문했던 좌표들에 대해 방문값을 초기화해줘야 가능한 모든 경우들에 대해 합산값을 구할 수 있다.

이는 다음 main 함수에서 DFS 메소드를 실행할 때와 DFS 메소드 자체에서 처리해줘야 한다.
main 함수에서 DFS 메소드가 실행되는 지점을 살펴보자.

for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                visited[i][j] = true;
                dfs(i,j,map[i][j],0);
                visited[i][j] = false; // 다시 초기화해주자
		/** 여기부터는 ㅗ 모양을 처리해준다 */
                if(i+1<N && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] ? map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] : max);
                if(i-2>=0 && j+1<M) max = (max<map[i][j]+map[i-1][j]+map[i-2][j]+map[i-1][j+1] ? map[i][j]+map[i-1][j]+map[i-2][j]+map[i-1][j+1] : max);
                if(i-1>=0 && j-2>=0) max = (max<map[i][j]+map[i][j-1]+map[i][j-2]+map[i-1][j-1] ? map[i][j]+map[i][j-1]+map[i][j-2]+map[i-1][j-1] : max);
                if(i+2<N && j-1>=0) max = (max<map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j-1] ? map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j-1] : max);
            }
        }

이렇게 해서 변형된 DFS와 추가로 ㅗ 모양까지 처리해주어 최댓값을 갱신해주면 된다.

아래는 내가 제출한 코드다.

import java.util.*;
import java.io.*;

public class boj14500 {
    static int N,M,max;
    static int[][] map = new int[500][500];
    static boolean[][] visited = new boolean[500][500];
    static int[] directionRow = { -1, 1, 0 , 0};
    static int[] directionCol = { 0 , 0, 1, -1};

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        N = Integer.parseInt(stk.nextToken());
        M = Integer.parseInt(stk.nextToken());
        for(int i=0; i<N; i++){
            stk = new StringTokenizer(bfr.readLine());
            for(int j=0; j<M; j++)
                map[i][j] = Integer.parseInt(stk.nextToken());
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                visited[i][j] = true;
                dfs(i,j,map[i][j],0);
                visited[i][j] = false;

                if(i+1<N && j+2<M) max = (max<map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] ? map[i][j]+map[i][j+1]+map[i+1][j+1]+map[i][j+2] : max);
                if(i-2>=0 && j+1<M) max = (max<map[i][j]+map[i-1][j]+map[i-2][j]+map[i-1][j+1] ? map[i][j]+map[i-1][j]+map[i-2][j]+map[i-1][j+1] : max);
                if(i-1>=0 && j-2>=0) max = (max<map[i][j]+map[i][j-1]+map[i][j-2]+map[i-1][j-1] ? map[i][j]+map[i][j-1]+map[i][j-2]+map[i-1][j-1] : max);
                if(i+2<N && j-1>=0) max = (max<map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j-1] ? map[i][j]+map[i+1][j]+map[i+2][j]+map[i+1][j-1] : max);
            }
        }

        bfw.write(String.valueOf(max));
        bfw.close();
    }

    static void dfs(int row, int col, int sum, int cnt){
        if(cnt==3){
            max = Math.max(max, sum);
            return;
        }

        for(int i=0; i<4; i++){
            int nRow = row + directionRow[i];
            int nCol = col + directionCol[i];

            if(nRow>=0 && nRow<N && nCol>=0 && nCol<M && !visited[nRow][nCol]){
                visited[nRow][nCol] = true;
                dfs(nRow, nCol, sum + map[nRow][nCol], cnt+1);
                visited[nRow][nCol] = false;
            }
        }
    }
}

시간 초과를 받는 건 언제나 짜릿하다. ㅎㅎ^^