[BOJ - JAVA] 14500 - 테트로미노 (브루트 포스)

# 주소

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

14500번: 테트로미노

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;

public class Main {
    static int n,m;
    static int[][] arr;
    static int[] dx = {-1,0,0,1};
    static int[] dy = {0,1,-1,0};
    static boolean[][] visit = new boolean[n][m];
    static int count;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new boolean[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dfs(i,j,0,0);
                check(i,j);
            }
        }
        System.out.println(count);
    }
    static void dfs(int x, int y, int depth, int sum){
        if(depth == 4){
            count = Math.max(count, sum);
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(visit[nx][ny])
                continue;
            visit[nx][ny] = true;
            dfs(nx,ny,depth+1,sum + arr[nx][ny]);
            visit[nx][ny] = false;
        }
    }
    static void check(int x, int y){
        int total = 4;
        int sum = arr[x][y];
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
            if(total < 3)
                return;
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m){
                total--;
                continue;
            }
            min = Math.min(min, arr[nx][ny]);
            sum += arr[nx][ny];
        }
        if(total == 4)
            sum = sum - min;
        count = Math.max(sum,count);
    }
}

제가 정말 약한 브루트포스 문제를 갖고왔습니다.

완전탐색이라 함은 빠지는 부분 없이 모든 인덱스에 대해 탐색을 할 수 있어야 하기 때문에 예외의 경우도 모두 상정할 수 있어야 합니다.

하지만 이 문제의 경우 DFS로 탐색할 때 ㅁ, ㅡ, ㅣ, ㄱ 모양 등은 탐색할 수 있지만

ㅗ, ㅜ, ㅏ, ㅓ 모양은 DFS로 만들 수 없습니다.

이 부분을 눈치챙기는게 굉장히 어려웠어서 다른 분들이 이해하고 푼 것을 최대한 흡수하려 했습니다.

일단 차근차근 살펴보겠습니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[n][m];
visit = new boolean[n][m];
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        arr[i][j] = scan.nextInt();
    }
}
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        dfs(i,j,0,0);
        check(i,j);
    }
}
System.out.println(count);

arr 배열과 visit배열을 선언하고 입력받습니다. 

그리고 이중 for문을 이용하여 각각의 인덱스에 대해 dfs문과 check문을 돌려서 각각의 테트로미노 모양에 대한 최대값을 구할 것입니다.

그러므로 dfs문을 먼저 살펴보겠습니다.

static void dfs(int x, int y, int depth, int sum){
    if(depth == 4){
        count = Math.max(count, sum);
        return;
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m)
            continue;
        if(visit[nx][ny])
            continue;
        visit[nx][ny] = true;
        dfs(nx,ny,depth+1,sum + arr[nx][ny]);
        visit[nx][ny] = false;
    }
}

dfs문은 여타 다른 백트래킹 문제와 상당히 비슷합니다.

dpeth가 4가 되면 count에 다 더했던 최댓값을 담아서 return하는 것이 목표입니다.

이 대 count에는 Math.max함수를 써서 최댓값을 갱신할 것입니다.

하지만 이 dfs문을 실행할 수 있다는 것은 ㅁ, ㅡ, ㅣ, ㄱ등 DFS문으로 충분히 만들 수 있는 모양입니다.

따라서 for문을 이용하여 nx와 ny를 만들고 만약 이 nx나 ny가 0보다 작거나 n,m보다 크거나 같을 때는 continue해주어 예외처리를 해주며 방문한 인덱스의 경우 continue해줍니다.

그리고 방문하지 않은 인덱스의 경우에 visit을 true로 바꾸고 dfs문을 새로 실행합니다.

이 때 depth를 +1해주어서 싣고 가고 sum에도 arr의 nx,ny인덱스의 값을 더해주어 실행합니다.

이를 통해 ㅁ, ㅡ, ㅣ, ㄱ, ㄴ 등 만들 수 있는 모든 모양은 이 dfs문을 통해 깔끔하게 더할 수 있습니다.

하지만 문제는 이 다음부터입니다.

ㅗ, ㅜ, ㅏ, ㅓ 모양은 이 dfs문으로 만들 수 없습니다.

그러므로 이와 별개로 check함수를 통해 구현해봅시다.

static void check(int x, int y){
    int total = 4;
    int sum = arr[x][y];
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < 4; i++){
        if(total < 3)
            return;
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= n || ny >= m){
            total--;
            continue;
        }
        min = Math.min(min, arr[nx][ny]);
        sum += arr[nx][ny];
    }
    if(total == 4)
        sum = sum - min;
    count = Math.max(sum,count);
}

테트로미노는 1x1의 정사각형이 4개 붙어 있는 도형 조각입니다.

그래서 total을 4로 두어 이 total이 4일 때를 계산할 것입니다.

무슨 말이냐면 nx, ny가 0보다 작거나 n,m보다 커지면 n X m 인덱스를 초과하잖아요?

그래서 이 테트로미노 조각이 인덱스를 초과해서 걸쳐져있는 부분에 대해서 total값을 깎음으로 별개의 작업을 거치지 않고 continue해주는 것입니다.

하지만 total이 3일 때는 계산이 가능합니다.

이건 또 무슨 의미일까요?

자 total이 3이란 것은 3칸이 연결되어 있다는 것인데, 이 때의 sum값은 당연히 3개의 점이 인접해있는 것의 arr값의 초오 합일 것입니다.

그러므로 ㅓ, ㅏ, ㅜ, ㅗ 모양은 구현이 어렵지만 저기에서 점을 하나 뺀 ㄴ이라던지 ㅣ 모양은 충분히 점 3개로 구현이 가능합니다.

그래서 그 때에는 따로 min값을 빼지 않고 그대로 sum을 출력하면 되는 것입니다.

또한 이 total이 3보다 작을 때는 굳이 계산을 안해주어도 되기 때문에 (어짜피 3일 때가 더 클 것이므로) 모두 return합니다.

자 그러므로 for문을 이용하여 이 nx와 ny를 모두 새로 점을 배정받은 뒤 min값에는 arr가 들어갈 수 있는 가장 최소값을 담고 그 때 sum에는 arr를 모두 더한 다음 마지막에 sum에서 min값을 뺀다면, 그리고 그 sum이 가장 큰 값이라면, 그때의 sum이 예외의 경우에서 가장 큰 값이 되는 것입니다.

 

처음에 이해하는게 어려웠습니다.

난이도도 높은 편은 아니라고 생각합니다.

브루트포스 문제를 아직 4~5개정도밖에 안풀어봤어서 아직 갈 길이 먼 거 같네요.

열심히해서 꼭 브루트포스도 마스터하겠습니다.

감사합니다.