테트리스 블럭 안의 합 최대화 하기 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

💡  풀이 방식

• DFS

1. 4개를 고르는 경우를 깊이 4짜리 백트래킹을 통해 뽑는다.

2. T자 모양 블럭의 경우, 따로 처리하는 메소드를 만든다.

 - 인접한 상하좌우 4칸 중 3개를 고르도록 한다.

 - 다음 재귀함수로 값을 가져갈 때도 현재 위치 (r,c)를 데려가게 한다.

comb(d + 1, depth + 1, r, c, sum + map[nr][nc]);

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0}; 
    static int[] dy = {0,0,-1,1};
 
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static int max = 0;
 
    public static void main(String[] args) 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());
 
        map = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        visited = new boolean[N][M];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                // 4개 뽑는 dfs
                visited[i][j] = true;
                dfs(i, j, 1, map[i][j]);
                visited[i][j] = false;
 
                comb(0, 0, i, j, map[i][j]);    // 인접한 4칸 중 3칸 고르기 (ㅗ,ㅓ,ㅏ,ㅜ 모양)
            }
        }
 
        System.out.println(max);
    }
 
    private static void dfs(int r, int c, int depth, int sum) {
        if(depth == 4) {
            max = Math.max(max, sum);
            return;
        }
 
        for(int d = 0 ; d < 4 ; d++) {    // 4방향 돌며 탐색
            int nr = r + dx[d];
            int nc = c + dy[d];
 
            if(!inRange(nr, nc) || visited[nr][nc])    continue;
 
            visited[nr][nc] = true;
            dfs(nr, nc, depth + 1, sum + map[nr][nc]);
            visited[nr][nc] = false;
        }
    }
 
    // T자 모양 처리
    private static void comb(int start, int depth, int r, int c, int sum) {
        if(depth == 3) {
            max = Math.max(max, sum);
            return;
        }
 
        for(int d = start ; d < 4 ; d++) {
            int nr = r + dx[d];
            int nc = c + dy[d];
 
            if(!inRange(nr, nc))    continue;
 
            comb(d + 1, depth + 1, r, c, sum + map[nr][nc]);    // 🔔 인자로 본인 위치 데려가기!!
        }
    }
 
    private static boolean inRange(int r, int c) {
        return (0 <= r && r < N && 0 <= c && c < M);
    }
}

 

 

 

 

---

💦 어려웠던 점

- T자형 모양은 어떻게 뽑아야할지 잘 모르겠었다.

 

 

🧐 새로 알게 된 내용

- T자형 모양 처리 방법 > (nr, nc)가 아닌 본인 위치 (r, c)를 가져간다.

⇒ WHY? 인접한 4칸 중 3칸을 선택하는 것이므로, 다음 재귀 호출에서는 현재 위치 (r, c)를 그대로 유지하고, 다음 방향을 선택하기 위해 d + 1로 인자 전달하는 것이다.

comb(d + 1, depth + 1, r, c, sum + map[nr][nc]);

 

1회독	2회독	3회독	4회독	5회독
V	0210

---

(참고)

✔ 테트로미노 문제랑 같다.

[백준/JAVA] 14500번: 테트로미노