[백준] (14500) 테트로미노

문제

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

사용 언어 : JAVA

---

---

내 생각

초기 생각

모든 N X M 칸을 돌면서 5가지 테트로미노를 모두 대조, 최댓값을 갱신한다.

근데 테트로미노의 블록들을 회전시키는 함수를 짜는게 까다로워서,, 그냥 회전으로 만들 수 있는 모든 모양을 2차원 배열로 만들어서 돌렸다.

그래서 이 정보를 담을 ArrayList<ArrayList<int[][]>> 를 생성하고 수기로 열심히 넣어줌

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_BJ_14500_테트로미노 {
    static int N, M, MAX = 0;
    static int[][] map;

    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());
            }
        }

        ArrayList<ArrayList<int[][]>> tetromino = new ArrayList<>(5);
        for (int i = 0; i < 5; i++) {
            tetromino.add(new ArrayList<>());
        }

        tetromino.get(0).add(new int[][] {{0, 1}, {0, 2}, {0, 3}});
        tetromino.get(0).add(new int[][] {{1, 0}, {2, 0}, {3, 0}});

        tetromino.get(1).add(new int[][] {{0, 1}, {1, 0}, {1, 1}});

        tetromino.get(2).add(new int[][] {{1, 0}, {2, 0}, {2, 1}});
        tetromino.get(2).add(new int[][] {{0, 1}, {0, 2}, {1, 0}});
        tetromino.get(2).add(new int[][] {{0, 1}, {1, 1}, {2, 1}});
        tetromino.get(2).add(new int[][] {{1, -2}, {1, -1}, {1, 0}});

        tetromino.get(2).add(new int[][] {{1, 0}, {2, 0}, {2, -1}});
        tetromino.get(2).add(new int[][] {{1, 0}, {1, 1}, {1, 2}});
        tetromino.get(2).add(new int[][] {{0, 1}, {1, 0}, {2, 0}});
        tetromino.get(2).add(new int[][] {{0, 1}, {0, 2}, {1, 2}});

        tetromino.get(3).add(new int[][] {{1, 0}, {1, 1}, {2, 1}});
        tetromino.get(3).add(new int[][] {{0, 1}, {1, -1}, {1, 0}});
        tetromino.get(3).add(new int[][] {{1, -1}, {1, 0}, {2, -1}});
        tetromino.get(3).add(new int[][] {{0, 1}, {1, 1}, {1, 2}});

        tetromino.get(4).add(new int[][] {{0, 1}, {0, 2}, {1, 1}});
        tetromino.get(4).add(new int[][] {{1, -1}, {1, 0}, {2, 0}});
        tetromino.get(4).add(new int[][] {{1, -1}, {1, 0}, {1, 1}});
        tetromino.get(4).add(new int[][] {{1, 0}, {1, 1}, {2, 0}});


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (ArrayList<int[][]> blocks : tetromino) {
                    for (int[][] block : blocks) {
                        int sum = func(block, i, j);
                        if (sum != -1){
                            MAX = Math.max(MAX, sum);
                        }
                    }
                }
            }
        }

        System.out.println(MAX);
    }

    private static int func(int[][] block, int i, int j) {
        int sum = map[i][j];
        int nr, nc;
        for(int[] pair: block) {
            nr = i + pair[0];
            nc = j + pair[1];
            if(nr < 0 || nc < 0 || N <= nr || M <= nc) return -1;
            sum += map[nr][nc];
        }
        return sum;
    }
}

 

개선

다른 사람의 코드를 구경하다가 내가 멍청이었음을 깨달았다.

바로 기준점에서 상하좌우로 중복되지 않게 4번 이동하면 저 5가지 테트로미노의 일반/회전/대칭 모양 중 반드시 하나가 나온다는 것. 당연함! 저 다섯가지 테트로미노가 4개의 작은 정사각형 블록으로 만들 수 있는 모든 형태이니까!

1. N X M 맵의 모든 위치에서 DFS 시작
2. DFS 함수에서 상하좌우로 이동하며 map 상의 숫자를 더해간다.
3. DFS의 depth가 4가 되면 MAX를 갱신

그런데 이렇게만 하면 凸 모양을 만들 수가 없다. 이를 해결하기 위해, depth가 2인 경우 아래처럼 작동한다.

dfs(curR, curC, sum, depth)

1. 맵 범위 내의 다음 진입 위치(nr, nc)를 구한다.

2. 만약 depth==2 라면
	
	1) visited[nr][nc] = true	// (nr, nc)를 포함했다 치고
    
	2) dfs(curR, curC, sum+map[nr][nc], depth+1) // 다른 (nr2, nc2)를 찾는다
    
	3) visited[nr][nc] = false	// 원위치

if(depth==2) 블록 내에서 위 과정을 실행한다.

 

최종 코드

package code;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BJ_14500_테트로미노 {
    static int N,  M, MAX = Integer.MIN_VALUE;
    static int[][] map;
    static boolean[][] visited;

    public static void main(String[] args) throws NumberFormatException, 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];
        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;
            }
        }

        System.out.println(MAX);
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static void dfs(int curR, int curC, int sum, int depth) {
        if(depth == 4) {
            MAX = Math.max(MAX, sum);
            return;
        }

        int nr, nc;
        for(int d = 0; d < 4; d++) {
            nr = curR + dr[d];
            nc = curC + dc[d];

            if(nr < 0 || nc < 0 || N <= nr || M <= nc || visited[nr][nc]) continue;

            // 凸 블록
            if(depth == 2) {
                // 이미 (nr, nc) 방문했다 치고
                visited[nr][nc] = true;
                // 현재 위치(curR, curC)에서 다른 (nr, nc)을 찾음
                dfs(curR, curC, sum + map[nr][nc], depth + 1);
                visited[nr][nc] = false;
            }

            visited[nr][nc] = true;
            dfs(nr, nc, sum + map[nr][nc], depth + 1);
            visited[nr][nc] = false;

        }
    }
}

---

느낀점

• 이런 블록 문제가 보이면 dfs로 치환해 봐야겠다