[백준/Java] 14391번: 종이 조각 - 비트마스크 완전탐색

14391 - 종이조각

링크텍스트

1. 문제

문제
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.
종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력
첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)
둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력
영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

요구사항

NxM 크기의 종이에 숫자들이 쓰여 있을 때, 이 종이를 가로 또는 세로로 잘라서 만들 수 있는 숫자들의 합의 최댓값을 구하는 문제이다.

• 입력: $N, M$ (최대 4), 그리고 종이의 숫자 정보.
• 조건:가로로 자르면 가로로 연속된 숫자가 하나의 수가 됨 (예: 1, 2 $\rightarrow$ 12).세로로 자르면 세로로 연속된 숫자가 하나의 수가 됨.
• 핵심 제약: $N, M$이 최대 4이다. 즉, 칸의 개수는 최대 16개 ($4 \times 4$).

접근 방식

처음에는 어떻게 잘라야 할지 감이 안 잡혀서 DFS나 복잡한 DP를 떠올렸습니다. 하지만 $N, M$이 매우 작다는 점에 주목했습니다.

핵심 아이디어: "각 칸은 가로(ㅡ) 아니면 세로(ㅣ), 딱 두 가지 상태만 가진다."

총 칸의 개수가 최대 16개이므로, 각 칸의 상태(가로/세로)를 0과 1로 표현하면 비트마스크(Bitmask)를 이용해 모든 경우의 수를 다 해볼 수 있습니다.

• 상태 표현:0: 가로로 이어지는 칸1: 세로로 이어지는 칸
• 경우의 수: $2^{N \times M}$ (최대 $2^{16} = 65,536$). 시간 제한 내에 충분히 계산 가능합니다.

구현 로직
1. 비트마스크 루프: 0부터 (1 << N*M) - 1까지 반복하며 종이를 자르는 모든 모양을 만듭니다.
2. 가로 합 계산:

• 이중 for문을 돌며 행(Row) 단위로 확인합니다.
• 비트가 0이면 cur = cur * 10 + num으로 숫자를 이어 붙입니다.
• 비트가 1이거나 행이 끝나면 sum += cur로 더하고 cur를 초기화합니다.

3. 세로 합 계산:

• 이중 for문을 돌며 열(Col) 단위로 확인합니다. (바깥쪽 루프가 j, 안쪽이 i)
• 비트가 1이면 숫자를 잇고, 0이거나 열이 끝나면 합산합니다.

4. 최댓값 갱신: 매 경우의 수마다 Math.max로 정답을 갱신합니다.

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < line.length(); j++) {
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        int answer = 0;
        for (int c = 0; c < (1 << N * M); c++) {
            int sum = 0;

            for (int i = 0; i < N; i++) {
                int cur = 0;
                for (int j = 0; j < M; j++) {
                    int pos = i * M + j;

                    if ((c & 1 << pos) == 0) {
                        cur = cur * 10 + arr[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }

            for (int j = 0; j < M; j++) {
                int cur = 0;
                for (int i = 0; i < N; i++) {
                    int pos = i * M + j;

                    if ((c & 1 << pos) != 0) {
                        cur = cur * 10 + arr[i][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }

            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }


}

느낀점

처음에는 비트마스크를 DP와 함께 사용하는 문제(TSP 등)만 접하다 보니, 이 문제도 어렵게 생각했었다. 하지만 이 문제는 DP가 아니라 비트마스크를 이용한 '완전 탐색' 문제였다.
가장 큰 수확:

• 단순히 코드를 베끼는 것이 아니라, "가로일 때 잇고, 세로일 때 끊는다"는 로직을 머릿속으로 정리한 뒤 코드로 옮기는 과정을 훈련할 수 있었다.

• 특히 "한 행/열이 끝났을 때(for문 종료 후) 남은 숫자(cur)를 더해주는 처리"를 놓치기 쉬운데, 이 부분을 스스로 잡아내면서 디테일한 구현력을 높일 수 있었다.

• $N, M$이 작을 때 비트마스크는 상태를 표현하는 아주 강력한 도구라는 것을 깨달았다.