💔 백준 14500 테트로미노

1. 문제 분석

백준 테트로미노 링크

2차원 배열에서 면 대 면으로 붙는 원소끼리 총 4개를 이었을 때, 원소간의 합이 최대값이 되는 경우를 구하여라.

2. 푸는 원리

테트로미노로 나올 수 있는 값들이 미리 나와 있다.

왼쪽 상단부터 1번이라고 하자. 그리고 왼쪽 -> 오른쪽으로 번호를 붙이겠다.
1번부터 4번에 해당하는 블럭은 DFS로 값을 구할 수 있다.
예를

들어보면,

 

다음과 같다. 하지만 5번의 경우 단순 dfs로 안 풀린다 왜냐하면 두번째 depth 부터 갈 수 있는 길이 2 갈래로 갈라지기 때문이다.

따라서 DFS로는 풀지 못하고, 중앙에서 시작하여 4방 탐색 중 3방을 고르는 조합으로 문제를 풀었다.

3. 코드 분석

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

/*
* 테트로미노
* 1 ~ 4번 패턴, dfs로 풀기 -> 모든 경우가 dfs로 나온다.
* 5번 패턴은 4개 중 3개의 점을 조합으로 구해서 풀기
* */

public class Main {


    static int N, M;
    static int [] idx = {-1,0,1,0};
    static int [] idy = {0,1,0,-1};
    static int [][] arr;

    static boolean [][] isVisited;

    static int max = 0;

    public static void main(String[] args) throws IOException {

        // 1. 값 입력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int [N][M];
        isVisited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
             st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 2. 계산
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                isVisited[i][j] = true;
                // 1 ~ 4 번 패턴 계산
                dfs(i,j,0,arr[i][j]);
                Combination(i,j,0,0,arr[i][j]);
                // 5번 패턴 계산

                isVisited[i][j] = false;
            }
        }

        System.out.println(max);
    }

    public static void dfs (int x, int y, int depth, int sum){

        // (1) 기저 조건
        if(depth == 3){
            max = Math.max(max, sum);
            return;
        }

        // (2) 계산 하는 곳
        for (int i = 0; i < 4; i++) {

            int nx = x + idx[i];
            int ny = y + idy[i];

            // 유효성 검증 -> dfs로 나아가려는 지점이 2차원 배열에 속하는 지점이면 유효함으로, 다음 DFS로 나아갈 자격이 있다.
            if (nx >= 0 && ny >= 0 && nx < N && ny < M){
                if(!isVisited[nx][ny]){
                    isVisited[nx][ny] = true;
                    dfs(nx,ny,depth+1, sum+arr[nx][ny]);
                    isVisited[nx][ny] = false;
                }
            }
        }
    }

    // 5번 패턴 용 조합

    public static void Combination (int x, int y, int depth, int start, int sum) {

        // (1) 기저 조건
        if(depth == 3){
            max = Math.max(max, sum);
            return;
        }


        // (2) 계산
        for (int i = start; i < 4; i++) {

            int nx = x + idx[i];
            int ny = y + idy[i];

            if( nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    Combination(x,y,depth+1, i+1, sum + arr[nx][ny]);
            }
        }
    }
}