자바(Java) 백준 14500 테트로미노 풀이

문제

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

14500번: 테트로미노

풀이

이 문제는 5가지의 도형중에서 분홍색 도형은 따로 해결해주고 나머지 4가지 도형은 dfs로 풀면 됩니다.

1) 나머지 도형
2차원 배열을 이중 for문으로 돌면서 각 점마다 dfs를 진행합니다. dfs는 첫번째 점 좌표를 넘겨주고 방문체크를 하면서 총 4개의 점을 방문 했을 때 합을 구해 최대값을 갱신해주면 됩니다.

2) 분홍색 도형
이 문제가 골드 5인 이유가 이 분홍색 도형을 따로 생각해서 풀어줘야 하기 때문으로 생각됩니다.
분홍색 도형은 dfs로는 찾을 수 가 없으므로 다른 방법으로 찾아줍니다.
제가 푼 방법은 다음과 같습니다.

1. 선택된 중심점이 두 벽면과 붙어있는 경우
   이 경우에는 분홍색 도형이 만들어 지지 않습니다.
2. 선택된 중심점이 한 벽면과 붙어있는 경우
   이 경우에는 한가지 도형만 만들 수 있습니다.
3. 선택된 중심점이 어떤 벽면과도 붙어있지 않은 경우
   도형을 회전 시키면 총 4가지의 도형을 얻을 수 있습니다.

제가 세운 조건식보다 좀 더 간단하게 푼 풀이들이 존재하므로 다른 코드도 참고해 보시면 좋을 거 같습니다. 중심점을 먼저 잡고 4가지 방향에서 각각 조건을 세워 해당 방향에서 도형을 만들 수 있는지 확인하는 풀이 방식도 있던데 이게 더 깔끔해 보입니다.

코드

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

public class Main {

    private static int n;
    private static int m;
    private static int[][] board;
    private static int max = Integer.MIN_VALUE;
    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    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());
        board = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int tmp = board[i][j];
                board[i][j] = -1;
                dfs(i, j, 0, 0);
                board[i][j] = tmp;
            }
        }

        //분홍색 도형을 구하기 위해 중심점이 2차원 배열 벽에 붙어있는지 아닌지 조건에 따라 구합니다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 2차원 배열 모서리에 중심점이 있는 경우
                if ((i == 0 && j == 0) || (i == 0 && j == m - 1) || (i == n - 1 && j == 0) || (i == n - 1 && j == m - 1)) {
                    continue;
                }
                int sum = 0;

                if (i == 0) {
                    // 윗쪽 벽에 중심점이 붙어있는 경우
                    sum = board[i][j] + board[i + dx[0]][j + dy[0]]
                            + board[i + dx[2]][j + dy[2]] + board[i + dx[3]][j + dy[3]];
                    max = Math.max(max, sum);
                } else if (i == n - 1) {
                    // 아랫쪽 벽에 중심점이 붙어있는 경우
                    sum = board[i][j] + board[i + dx[1]][j + dy[1]] + board[i + dx[2]][j + dy[2]]
                            + board[i + dx[3]][j + dy[3]];
                    max = Math.max(max, sum);
                } else if (j == 0) {
                    // 왼쪽 벽에 중심점이 붙어있는 경우
                    sum = board[i][j] + board[i + dx[0]][j + dy[0]] + board[i + dx[1]][j + dy[1]]
                            + board[i + dx[2]][j + dy[2]];
                    max = Math.max(max, sum);
                } else if (j == m - 1) {
                    // 오른쪽 벽에 중심점이 붙어있는 경우
                    sum = board[i][j] + board[i + dx[0]][j + dy[0]] + board[i + dx[1]][j + dy[1]]
                            + board[i + dx[3]][j + dy[3]];
                    max = Math.max(max, sum);
                } else {
                    // 중심점이 어떤 벽에도 붙어있지 않은 경우
                    sum = board[i][j] + board[i + dx[0]][j + dy[0]] + board[i + dx[1]][j + dy[1]]
                            + board[i + dx[2]][j + dy[2]] + board[i + dx[3]][j + dy[3]];
                    for (int d = 0; d < 4; d++) {
                        sum -= board[i + dx[d]][j + dy[d]];
                        max = Math.max(max, sum);
                        sum += board[i + dx[d]][j + dy[d]];
                    }
                }
            }
        }

        System.out.println(max);
    }

    public static void dfs(int a, int b, int cnt, int sum) {
        if (cnt == 4) {
            max = Math.max(max, sum);
            return;
        }

        // 분홍색 도형을 제외한 나머지 도형들을 dfs를 사용하여 구합니다.
        for (int d = 0; d < 4; d++) {
            int newA = a + dx[d];
            int newB = b + dy[d];
            if (newA < 0 || newA >= n || newB < 0 || newB >= m || board[newA][newB] == -1) {
                continue;
            }
            int tmp = board[newA][newB];
            board[newA][newB] = -1;
            dfs(newA, newB, cnt + 1, sum + tmp);
            board[newA][newB] = tmp;
        }
    }
}