14500번: 테트로미노

문제

크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 합니다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있습니다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어집니다. (4 ≤ N, M ≤ 500) 둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어집니다.
• 출력: 테트로미노가 놓인 칸의 수들의 합의 최댓값을 출력합니다.

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

풀이: 전역 방문 배열을 활용한 백트래킹 완전 탐색

• DFS와 백트래킹: 임의의 칸에서 시작하여 상하좌우로 4번 연속 이동(DFS)하면, 테트로미노 5가지 모양 중 'ㅗ' 모양을 제외한 4가지 모양(회전 및 대칭 형태 포함)이 자연스럽게 모두 만들어집니다. 이때 탐색을 진행하기 전 방문 처리를 하고(visited[ny][nx] = true), 탐색이 끝나고 되돌아올 때 방문 처리를 해제(visited[ny][nx] = false)하는 백트래킹 기법을 사용하여 하나의 전역 배열만으로 모든 경우의 수를 처리할 수 있습니다.
• 'ㅗ' 모양 예외 처리: 'ㅗ' 모양(ㅏ, ㅓ, ㅗ, ㅜ)은 한붓그리기(DFS)로 만들 수 없는 유일한 모양입니다. 따라서 반복문 내에서 시작점을 교차점으로 두고 4방향 중 3방향의 날개를 검사하는 4가지 하드코딩된 조건문으로 별도 처리하여 최댓값을 갱신합니다.

코드

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

public class Main {
    static int n, m, ans;
    static int[][] a;
    
    static boolean visited[][];
    
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, 1, 0, -1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        a = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                a[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++) {
                // 1. 일반적인 4칸 연속 도형 탐색 (DFS + 백트래킹)
                visited[i][j] = true;
                dfs(i, j, a[i][j], 1);
                visited[i][j] = false; // 원상 복구

                // 2. 'ㅗ' 모양 예외 처리 (ㅏ, ㅜ, ㅗ, ㅓ)
                if (i - 1 >= 0 && i + 1 < n && j + 1 < m) {
                    ans = Math.max(ans, a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j + 1]);
                }
                if (i + 1 < n && j - 1 >= 0 && j + 1 < m) {
                    ans = Math.max(ans, a[i][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1]);
                }
                if (i - 1 >= 0 && j - 1 >= 0 && j + 1 < m) {
                    ans = Math.max(ans, a[i][j] + a[i - 1][j] + a[i][j - 1] + a[i][j + 1]);
                }
                if (i - 1 >= 0 && i + 1 < n && j - 1 >= 0) {
                    ans = Math.max(ans, a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j - 1]);
                }
            }
        }

        bw.write(ans + "");
        bw.flush();
    }

    static void dfs(int y, int x, int sum, int depth) {
        // 4칸을 모두 채웠을 경우 최댓값 갱신 후 종료
        if (depth == 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            // 범위를 벗어나거나 이미 방문한 칸은 패스
            if (ny >= n || nx >= m || ny < 0 || nx < 0 || visited[ny][nx]) {
                continue;
            }

            visited[ny][nx] = true;
            dfs(ny, nx, sum + a[ny][nx], depth + 1);
            // 탐색 후 다른 모양을 만들기 위해 방문 상태 원상 복구 (백트래킹)
            visited[ny][nx] = false;
        }
    }
}

알고리즘 분류

구현 (Implementation), 브루트포스 알고리즘 (Brute Force), 깊이 우선 탐색 (DFS), 백트래킹 (Backtracking)