백준 14500 테트로미노 - JAVA

14500 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

< DFS 분기 탐색 >

import java.io.*;
import java.util.*;
 
public class Main {
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};
    private static int[][] arr;
    private static boolean[][] visit;
    private static int N, M, max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visit = 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());
            } 
        } 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = true;
                dfs(i, j, 1, arr[i][j]);
                visit[i][j] = false;
            } 
        }
        bw.write(String.valueOf(max));
        bw.flush();
    }
    private static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, 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) {
                if (!visit[nx][ny]) { 
                    visit[nx][ny] = true;
                    // T자를 위한 분기 1번
                    if (depth == 2) {
                        dfs(x, y, depth+1, sum+arr[nx][ny]);
                    }
                    // 일반 모양 분기 2번
                    dfs(nx, ny, depth+1, sum+arr[nx][ny]);
                    // depth==2에서 뻗어나온 두 분기를 한번에 false처리하여 depth == 2를 종료
                    visit[nx][ny] = false;
                }
            } 
        } 
    }
}

 

< DFS + checkTshape 탐색 >

import java.io.*;
import java.util.*;
 
public class Main {
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};
    private static int[][] arr;
    private static boolean[][] visit;
    private static int N, M, max = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visit = 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());
            } 
        } 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = true;
                dfs(i, j, 1, arr[i][j]);
                visit[i][j] = false;
                checkTshape(i, j);
            } 
        }
        bw.write(String.valueOf(max));
        bw.flush();
    }
    private static void dfs(int x, int y, int depth, int sum) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        } 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isInBounds(nx, ny)) {
                if (!visit[nx][ny]) { 
                    visit[nx][ny] = true;
                    dfs(nx, ny, depth+1, sum+arr[nx][ny]);
                    visit[nx][ny] = false;
                }
            } 
        } 
    }
    private static void checkTshape(int x, int y) {
        int center = arr[x][y];
        for (int i = 0; i < 4; i++) {
            int temp = center;
            boolean isValid = true;
            for (int j = 0; j < 4; j++) {
                if (i == j) continue; 
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (!isInBounds(nx, ny)) {
                    isValid = false;
                    break;
                }
                temp += arr[nx][ny];
            } 
            if (isValid) max = Math.max(max, temp);
        } 
    }
    private static boolean isInBounds(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

 

알고리즘 설명

---

테트로미노의 모양은 각 I, O, Z, L, T 모양이 존재합니다. → https://namu.wiki/w/테트리스/용어#s-3.1 참고

문제에서 주어진 조건대로, 각 모양은 회전과 대칭이 가능합니다. 하지만 모든 모양의 모든 경우를 일일이 좌표로 탐색하는 것은 매우 비효율적입니다. 각 모양들을 유심히 보고있으면, T 모양을 제외한 나머지 모양들은 모두 블록이 연속적으로 연결된 형태라는 공통점이 있습니다. 이 점을 활용하면, DFS를 이용해 시작점에서부터 인접한 블록을 따라 최대 4칸(depth 4)까지 탐색하면서 I, O, Z, L 모양의 회전 및 대칭 형태를 효과적으로 탐색할 수 있습니다.

하지만 T 모양은 중심블록에서 각 3방향으로 퍼지는 구조이므로, 한번의 DFS 방식으로 완전히 탐색하기는 불가능합니다.

따라서 T모양의 탐색은

1. I, O, Z, L에 대한 DFS탐색 중간에, T 모양이 나올 수 있는 DFS분기를 만들어 추가 탐색
2. 각 좌표에서 ㅗ,ㅜ,ㅓ,ㅏ 모양을 검사하는 메서드를 따로 만들어 탐색 (DFS + checkTshape 탐색)

위처럼, 크게 두가지로 탐색방식을 나눌 수 있습니다.  1번의 경우 코드자체는 짧지만, T자 모양검사의 중복되는 검사가 존재하므로, 효율성만 놓고 본다면 2번이 효율적인 풀이 방식이라고 할 수 있겠습니다.

 

1번의 경우 어떠한 중복 탐색이 발생할 수 있는지 간단하게 살펴보고 넘어가겠습니다.

위의 그림은 depth == 2가 depth == 1에 대해 오른쪽으로 탐색을 진행했을 때, depth == 3을 각각 위, 오른쪽, 아래로 탐색된 경우를 나타낸 그림입니다.

depth == 1이 모두 같은 위치(3, 3)라고 가정할때,

depth == 3이 위로 탐색되고 depth == 4가 오른쪽으로 탐색된 경우(depth == 4-1)와

depth == 3이 오른쪽으로 탐색되고 depth == 4가 위쪽으로 탐색된 경우(depth == 4 - 1)가 같은 좌표와 같은 모양인 것을 알 수 있습니다. 즉, 같은 탐색을 두 번 진행한 것임을 알 수 있습니다. 빨간색으로 표시된 경우에도 동일한 탐색을 두 번 진행함을 알 수 있습니다.

다른 경우도 살펴보겠습니다.

왼쪽의 탐색은 (3,3)에서 시작하고, 오른쪽의 탐색은 (3,5)에서 시작한다고 가정한 경우, 파란색과 빨간색의 경우 모두 같은 탐색을 두 번 진행함을 알 수 있습니다.

위의 결과들을 미루어보아, 생각보다 많은 중복탐색이 진행되는 것을 알 수 있습니다. 따라서 중복 탐색이 발생하지 않는 2번(각 좌표에서 ㅗ,ㅜ,ㅓ,ㅏ 모양을 검사하는 메서드를 따로 만들어 탐색)이 효율적인 탐색 방식임을 알 수 있습니다.

아래는, 각 탐색 방식에 따른 결과입니다.

DFS 분기 탐색

DFS + checkTshape 탐색

 

코드 해석

---

 

 

2번의 경우를 기준으로 설명드리겠습니다.

먼저 입력을 통해 2차원 배열을 구성한 후, 각 위치를 시작점으로 하여 4방향으로 이동하면서 inBounds 메서드를 사용해 배열 인덱스 범위를 벗어나지 않는지 확인하고, 깊이가 4가 될 때까지 재귀적으로 탐색하며, 각 경로에서의 합을 계산하고 최대값을 갱신합니다.

동시에 checkTshape메서드도 진행하여 T모양을 탐색합니다. 중심에서 네 방향 중 하나를 제외한 세 방향의 합을 계산하며, 해당 방향이 모두 범위 내에 있을 때만 값을 누적하여 최대값을 갱신합니다. 이때 inBounds 메서드를 사용해 배열 인덱스 범위를 벗어나지 않는지 확인하며 진행합니다.

 

전체적으로 각 위치에 대해 DFS와 T자 탐색을 각각 수행하며, max의 값을 계산하여 max의 최댓값을 갱신합니다. 모든 탐색이 종료되면, max를 출력합니다.