[백준] 종이 조각 (14391) Java

문제 링크

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

14391번: 종이 조각

 

문제 요약

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 

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

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

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

 

출력

조각의 합의 최댓값을 출력한다.

 

접근법

N과 M의 크기가 최대 4로 매우 작고, 제한시간도 2초고, 최댓값만 구하면 되는 걸 보니 완전탐색을 통한 브루트포싱의 각이 보인다.

문제는 "종이를 가로 혹은 세로 직사각형의 형태로 겹치지 않고 자르는 모든 경우"를 탐색하는 것을 어떻게 구현하냐이다.

 

처음에는 도저히 모르겠어서 삽질을 하다가 구글링을 했는데, 생각보다 너무 간단한 아이디어였다.

전체 종이를 보지 말고, 각 칸을 기준으로 보면 문제가 아주 쉬워진다.

 

각 칸의 입장에서 보면, 종이가 어떻게 찢기든지 상관 없이

자기 자신은 결과적으로 가로로 찢기는 칸이거나(가로 형태의 직사각형 안에 포함되는 칸이거나), 세로로 찢기는 칸 (세로 형태의 직사각형 안에 포함되는 칸) 이 두 경우밖에 없다.

 

즉 종이를 2차원 배열 형태로 저장하고,

각 칸에 한 번은 가로, 그 다음엔 세로로 표시해나가며 DFS를 돌아서

모든 칸에 가로 혹은 세로 표시를 다 했을 때마다 해당 상황에서의 숫자의 합을 구한 뒤, 그 값들 중 최대값을 출력하면 그것이 정답이다.

 

예를 들어 문제의 예시처럼 종이를 자른 경우를 다음과 같이 표현할 수 있다.

DFS를 모든 칸에 대해서 돌아서 가로 혹은 세로를 위처럼 전부 다 채울 때마다,

가로의 경우 각 행 단위로 반복문을 돌며 숫자를 만들어서 가로 숫자에 대한 합을 구하고,

세로의 경우 각 열 단위로 반복문을 돌며 숫자를 만들어서 세로 숫자에 대한 합을 구한다음,

두 합을 합치면 전체 종이에 대한 합이 나온다. 이 합을 모든 종이를 찢는 경우에 대해 구해서 최댓값을 찾으면 그게 정답이라는 것이다.

 

실제로 구현할 때는 가로/세로가 아닌 boolean 형태로 true/false로 구현하면 편할 것이다.

 

근데 여기서 비트마스킹을 적용해서 재귀 호출을 통한 DFS가 아닌 단순 반복문으로 위 과정을 조금 더 쉽게 구현할 수 있다.

문제 자체가 복잡한 브루트포싱은 아니어서 두 방법 다 코드의 복잡도는 비슷한 것 같은게 함정이지만 말이다 ㅎㅎ...

 

위에서 각 칸은 가로 혹은 세로의 경우의 수만 가진다고 했는데, 이 가로와 세로를 각각 0과 1로 바꿔주면

 

이렇게 표현이 가능하다.

근데 위 그림은 2차원이지만, 이 2차원을 1차원으로 쭉 늘려서 숫자 하나 하나를 그대로 옮겨 적으면

0001110111110011 이렇게 16자리수의 bit로 표현할 수 있다.

 

그런데 각 칸은 가로 혹은 세로, 다시 말하면 0 혹은 1의 경우만 가질 수 있으므로

0부터 2^16 -1 (1이 16개 있는 이진수) 사이의 값으로 모든 경우를 표현할 수 있다는 것이다.

 

이 것을 적용해서 비트마스킹으로 모든 경우를 탐색하며 합을 구하면 문제를 풀 수 있다.

 

유의할 점은 비트마스킹을 쓰면 숫자를 만들고 합을 구할 때 비트마스크에 비트 연산(<<, >>, &, ~ 등)을 수행해야 하므로, 코드 구조는 간단해지지만 가독성은 조금 떨어지는 경향이 있다는 것이다. 이 부분 때문에 구현하기 전에 고민도 많이 하고, 구현 하면서도 좀 긴가 민가 하면서 구현했다. 

 

 

시간 복잡도

각 칸이 가로 혹은 세로의 2가지 경우를 가질 수 있고, 모든 경우를 다 따져줘야 하므로

O(2^(N * M)) 인데 N과 M의 최댓값이 4이므로 O(2^16).

 

 

공간 복잡도

N * M * sizeof(int) bytes 면 충분하다.

 

 

풀면서 놓쳤던 점

굳이 비트마스킹을 안하고, DFS를 통한 완전 탐색으로도 풀 수 있다는 사실은 바로 알아챘다.

문제는 구현에 대해서는 접근법이 틀렸다는 것이다.

 

각 칸이 가로 또는 세로의 두가지 경우를 가질 수 있다는 것을 기반으로 완전 탐색을 해야 하는데,

각 칸의 숫자를 시작 숫자로 해서 숫자를 가로 혹은 세로로 확장시켜 나가면서 완전 탐색을 하려니까 구현이 너무 까다로워졌다.

(예를 들어 문제 예시의 첫 행애서 4, 49, 493, 4937, 42, 423, 4239 이렇게 가로 세로로 확장시킬 수 있는 모든 경우에 대해서 DFS를 수행하게끔 구현하려고 했다)

 

뭔가 단순히 이런 알고리즘을 쓰면 되겠다 같은 것 보다, 이런 관점이나 아이디어가 생각보다 중요하구나 싶었다.

 

 

이 문제에서 얻어갈 점

비트마스킹 구현과 적용. 합을 구하는 과정에서 비트마스크를 잘 다뤄야 하는데, 이 부분이 어색해서 많이 헷갈렸다.

이 문제를 통해 익숙해질 수 있었다.

 

 

코드

import java.util.*;

public class Main
{
    static int rows, cols;
    static Scanner sc;

    public static void main(String[] args)
    {
        sc = new Scanner(System.in);
        StringTokenizer st;

        st = new StringTokenizer(sc.nextLine());
        rows = Integer.parseInt(st.nextToken());
        cols = Integer.parseInt(st.nextToken());

        //종이의 숫자들을 2차원 배열 형태로 입력받음
        int[][] paper = new int[rows][cols];
        readPaper(paper);

        System.out.println(getMaxSum(paper));
    }

    static int getMaxSum(int[][] paper)
    {
        int maxSum = 0; //반환할 값
        int bitmaskMax = 1 << rows * cols; //bitmask의 최대값 + 1

        //rows * cols 길이의 bitmask를 이용해서 종이를 찢는 모든 경우를 브루트포싱함
        //bit가 0인 칸은 가로로 찢는 칸, 1인 칸은 세로로 찢는 칸임
        for (int bitmask = 0; bitmask < bitmaskMax; bitmask++)
        {
            int sum = 0;
            int num;

            //bitmask의 각 bit를 맨 왼쪽 bit부터 차례로 검사하기 위한 변수
            //bitmask와는 다르게 항상 1인 bit가 한개만 존재함에 유의
            int bitIdx = 1 << (rows * cols - 1);
            //가로로 찢는 칸이 0을 의미하므로 not 연산을 통해 0을 1로 만들어줌
            bitmask = ~bitmask;

            //가로로 찢은 숫자들의 합을 구하는 반복문
            for (int row = 0; row < rows; row++)
            {
                num = 0;
                for (int col = 0; col < cols; col++)
                {
                    //bitmask는 2차원이 아닌 1차원의 연속된 bit이므로
                    //이런식으로 bitIdx를 움직이며 검사를 해 주며 숫자를 만들어야 한다
                    if ((bitmask & (bitIdx >> row * cols + col)) != 0)
                    {
                        num *= 10;
                        num += paper[row][col];
                    }
                    //bitmask에서 0인 bit를 만났을 경우 가로로 찢은 숫자가 끝난것이므로
                    //sum에 더해줘야 한다
                    else
                    {
                        sum += num;
                        num = 0;
                    }
                }
                //col == cols가 되어서 끝나는 경우도 있으므로 sum에 더해줘야 함을 잊지 말자
                sum += num;
            }

            bitIdx = 1 << (rows * cols - 1);
            bitmask = ~bitmask; //다시 not 연산을 해서 이제 세로로 찢은 칸을 찾는다

            //이번엔 가로가 아니라 세로로 봐야 하므로 반복문의 row와 col이 바뀌어야 한다
            for (int col = 0; col < cols; col++)
            {
                num = 0;
                for (int row = 0; row < rows; row++)
                {
                    if ((bitmask & (bitIdx >> row * cols + col)) != 0)
                    {
                        num *= 10;
                        num += paper[row][col];
                    }
                    else
                    {
                        sum += num;
                        num = 0;
                    }
                }
                sum += num;
            }

            //모든 bitmask 경우를 다 살펴보며 maxsum을 구한다
            maxSum = Math.max(maxSum, sum);
        }

        return maxSum;
    }

    static void readPaper(int[][] paper)
    {
        String line;
        for (int i = 0; i < rows; i++)
        {
            line = sc.nextLine();
            for (int j = 0; j < cols; j++)
                paper[i][j] = line.charAt(j) - '0';
        }
    }
}