[코드트리/INTERMEDIATE LOW] 트로미노 (JAVA)

📖 문제

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

 

 

 

💡  풀이 방식

• DFS

해당 점을 포함해 3개를 뽑는 DFS 함수를 작성한다.

점들의 합을 변수로 가지고 다니며 3개를 뽑았을 때 이 값과 최댓값을 비교해 더 큰 값으로 최댓값을 갱신한다.

 

 

 

🔺 코드

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 = Integer.MIN_VALUE;
 
    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++) {
                if(!visited[i][j]) {
                    visited[i][j] = true;
                    dfs(i, j, 1, map[i][j]);
                    visited[i][j] = false;
                }
            }
        }
 
        System.out.println(max);
    }
 
    private static void dfs(int x, int y, int depth, int sum) {
        if(depth == 3) {
            max = Math.max(max, sum);
            return;
        }
 
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(!inRange(nx, ny) || visited[nx][ny]) continue;
 
            visited[nx][ny] = true;
            dfs(nx, ny, depth + 1, sum + map[nx][ny]);
            visited[nx][ny] = false;
        }        
    }
 
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}

 

 

➕ 다른 풀이 방식

- 가능한 모든 경우에 대해 직접 작성해 브루트포스로 풀 수도 있다.

 

---

💦 어려웠던 점

- 테트로미노 며칠 동안 여러 번 풀다보니 익숙해져서 10분 컷 했다ㅠㅠ

 

 

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

---

(참고)

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