[JAVA/구현] 백준 14500 테트로미노

1. 문제

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

14500번: 테트로미노

 

2. 풀이

• 총 5개의 블록이 있는데, 이 중 ㅜ 블록(분홍색 블록)을 제외하고는 DFS 4번을 통해 대칭, 회전을 한 모든 블록의 모습을 구할 수 있다.
  • 따라서, ㅜ를 제외한 4개의 블록은 DFS를 통해 4개 칸의 합을 구하고, ㅜ는 별도의 함수를 통해 4개 칸의 합을 구한다.
• 모든 칸에서 4개 블록타입을 모두 확인해야 하므로, 처음 DFS를 호출 할 때 백트래킹을 사용한다.(81~83줄)
  •  DFS 함수 내에서도, 4가지 블록타입을 모두 확인하기 위해 백트래킹을 사용한다.(55~57줄)
• 모든 칸에서 ㅜ 블록에 대한 합을 구해야 하므로, 모든 칸에 대해서 ㅗ 블록일 경우를 체크하는 함수를 호출한다.(getOhCase())

 

3. 코드

 

import java.util.*;
import java.io.*;

class Main{
    
    // 테트로미노
    
    static int n, m;
    static int[][] map;
    static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    static int[][][] ohCase = {
            {{0,0},{0,-1},{0,1},{-1,0}}, // ㅗ
            {{0,0},{0,-1},{0,1},{1,0}}, // ㅜ
            {{0,0},{-1,0},{1,0},{0,1}}, // ㅏ
            {{0,0},{-1,0},{1,0},{0,-1}} // ㅓ
        };
    static int max = 0;
    static boolean[][] visited;
    
    public static boolean isInRange(int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < m);
    }
    
    // ㅗ 블록일 경우 체크
    public static void getOhCase(int x, int y) {
        for(int i = 0; i < 4; i++) {
            boolean isRight = true;
            int sum = map[x][y];
            for(int j = 1; j < 4; j++) {
                int nX = x + ohCase[i][j][0];
                int nY = y + ohCase[i][j][1];
                if(!isInRange(nX, nY)) {
                    isRight = false;
                    break;
                }
                if(isRight) sum += map[nX][nY];    
            }
            max = Math.max(max, sum);
        }
    }
    
    // dfs를 통해 ㅗ를 제외한 4개 블록을 체크
    public static void dfs(int x, int y, int score, int blockCnt) {
        
        if(blockCnt == 4) {
            max = Math.max(max, score);
            return;
        }
        
        for(int i = 0; i < 4; i++) {
            int nX = x + dir[i][0];
            int nY = y + dir[i][1];
            if(!isInRange(nX, nY)) continue;
            if(!visited[nX][nY]) {
                visited[nX][nY] = true;
                dfs(nX, nY, score + map[nX][nY], blockCnt + 1);
                visited[nX][nY] = false;
            }
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        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];
        visited = new boolean[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());
            }
        }
        
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                visited[i][j] = true;
                dfs(i, j, map[i][j], 1);
                visited[i][j] = false;
                
                getOhCase(i, j);
            }
        }
        
        System.out.println(max);
    }
}