백준 14500번 : 테트로미노

백준 14500번 : 테트로미노

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int[][] paper = null;
    boolean[][] check = null;
    int result = 0;
    int n = 0;
    int m = 0;

    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public void solution() throws IOException {
        initPaperAndCheck();

        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                check[i][j] = true;
                dfs(i, j, paper[i][j], 1);
                check[i][j] = false;
            }
        }
        System.out.println(result);
    }

    public void dfs(int x, int y, int sum, int length){
        if(length==4){
            result = Math.max(result, sum);
            return;
        }
        for(int i = 0; i<4; i++){
            int currentX = x + dx[i];
            int currentY = y + dy[i];

            if(currentX < 0 || currentX >= n || currentY < 0 || currentY >= m) continue;

            if(!check[currentX][currentY]){

                if(length==2){
                    check[currentX][currentY] = true;
                    dfs(x, y,sum+paper[currentX][currentY], length+1);
                    check[currentX][currentY] = false;
                }
                check[currentX][currentY] = true;
                dfs(currentX, currentY, sum+paper[currentX][currentY], length+1);
                check[currentX][currentY] = false;
            }
        }
    }

    public void initPaperAndCheck() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        paper = new int[n][m];
        check = new boolean[n][m];
        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<m; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

문제만 보고선 너무 어지러웠다. 특정 모양의 테트로미노들 만큼  대칭,회전까지 함수로 만들어서 돌릴 생각부터 했다. 처음에 제일 쉬운 직선부터 만들어서 가로, 세로 체크하는 함수를 만들다가... '아니 이건 아닌거 같아...' 라는 생각이 들었고, 구글링 했다. 처음엔 구글링을 봐도 이해가 안됐다. 결국 풀이는 DFS 알고리즘으로 풀어야 한다는데... DFS는 또 무엇인지지... 코드를 봐도 이해가 안됐지만, 친구의 사진 한장으로 이해했다. 직접 선으로 그어준 사진이었는데. 이래서 유명한 강의들 보면 직접 그려보라는 얘기가 있는거 같다. 정답은 정사각형 4개는 어떤 방식으로 붙여도 결국엔 테트로미노라는 것이다. 

 

출처이미지원본(https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8) 직접 그려준 친구의 따뜻한 손길

한 점에서 시작해 변이 닿는 동서남북 한 곳을 이동한다. 그 곳에서 다시 동서남북을 이동한다. 그렇게 4번을 반복해서

전진하다보면 완성된 모양은 테트로미노의 도형중 한 가지이다. 여기서 중요한 점은 꼭 4가지의 정사각형이 이어져야 하기 때문에 동서남북으로 한칸씩 이동하지만 이 전에 왔던 곳은 다시 이동하면 정사각형 2개,3개,1개의 모양으로 마무리가 될 수도 있기 때문에 지나온 곳은 되돌아가지 못하게 해준다. 그리고  ㅏ ㅜ ㅓ ㅗ 모양 같은 경우는 지나온 곳을 다시 돌아야하기 때문에 다르게 처리해주어야한다. 만약 현재의 칸이 두 번째로 이동한 칸이라면, 두 번째에서 다시 한번 탐색하는 방법을 사용했다.