BOJ 14500 - 테트로미노

14500번: 테트로미노 (acmicpc.net)

 

폴리오미노란 크기가 1x1인 정사각형을 여러 개 이어서 붙인 도형이며 다음을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

NxM인 종이 위에 4개의 정사각형으로 이루어진 폴리오미노인 테트로미노 하나를 놓으려 한다.

적절히 놓아 칸에 쓰여 있는 수들의 합을 최대를 찾아라

 

일종의 그래프 문제이다. 연결되어 있다는 것 자체가 두 노드 사이에 간선이 존재한다는 뜻이다.

꼭짓점 조건에 따라 대각선은 제외되고 상하좌우만 판단하게 된다.

예를 들어 테트로미노는 시작점 1개를 기준으로 총 3개의 노드를 상하좌우로 탐색해 나간 것이다.

단순한 방법으로는 NxM 크기의 배열을 순회하며 시작점을 정하고 해당 시작점에서 탐색을 하는 방법이 있다. 테트로미노이기 때문에 4개의 노드를 탐색하면 된다.

 

그런데 여기서 문제가 발생한다.

dfs로 탐색하게 되면 T 모양의 형태를 탐색할 수가 없다.

T모양을 어떻게 판단할 수 있을까? 그냥 별도로 처리하자.

나머지 모든 모양들은 dfs로 처리가 가능하며 T모양만 별도로 구성해 처리를 하겠다.

T모양을 어떻게 별도로 처리할까?

우선 현재 위치에서 상하좌우 중 3방향을 고르면 된다.

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

public class Main {

    static FastReader scan = new FastReader();
    static int N, M;
    static int[][] board;
    static int[][] DIRECTION = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int max = 0;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        board = new int[N][M];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                board[r][c] = scan.nextInt();
            }
        }
    }

    static void dfs(int depth, int r, int c, int sum, boolean[][] visited) {
        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int d = 0; d < 4; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                continue;
            }
            if (visited[nr][nc]) {
                continue;
            }
            visited[nr][nc] = true;
            dfs(depth + 1, nr, nc, sum + board[nr][nc], visited);
            visited[nr][nc] = false;
        }
    }

    static void checkTShape(int r, int c) {
        // 현재 위치 r,c 에서 3가지 방향을 정해야한다. -> 어차피 최대를 찾아야 하므로 4방향을 다 보고 최소값을 -1 하자.
        int min = Integer.MAX_VALUE;
        int count = 0;
        int sum = board[r][c];

        for (int d = 0; d < 4; d++) {
            int nr = r + DIRECTION[d][0];
            int nc = c + DIRECTION[d][1];

            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            sum += board[nr][nc];
            min = Math.min(min, board[nr][nc]);
            count++;
        }

        if (count == 3) {
            // 딱 T 모양을 만드는 경우
            max = Math.max(sum, max);
        } else if (count == 4) {
            // 4방향 모두 탐색 가능
            max = Math.max(sum - min, max);
        }
    }

    public static void main(String[] args) {
        input();
        boolean[][] visited = new boolean[N][M];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                visited[r][c] = true;
                dfs(1, r, c, board[r][c], visited);
                visited[r][c] = false;
                checkTShape(r, c);
            }
        }

        System.out.println(max);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

}