14391 종이 조각

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 입력 2

2 2
99
11

예제 출력 2

182

예제 입력 3

4 3
001
010
111
100

예제 출력 3

1131

예제 입력 4

1 1
8

예제 출력 4

8

코드

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

public class P_14391 {
    static int[]        wl;
    static int[][]      info;
    static int[][]      wid_or_len;
    static boolean[][]  visited;
    static int          max = Integer.MIN_VALUE;

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

        wl = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        info = new int[wl[0]][wl[1]];
        for (int i = 0; i < wl[0]; i++) info[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
        wid_or_len = new int[wl[0]][wl[1]];
        visited = new boolean[wl[0]][wl[1]];

        piece_of_paper(0);
        bw.write(Integer.toString(max));
        bw.flush();
    }

    public static void piece_of_paper(int cnt) {
        if (cnt == wl[0] * wl[1]) {

            for (int i = 0 ; i < wl[0]; i++) Arrays.fill(visited[i], false);

            int result = find_max_score();
            max = (max > result) ? max : result;
        }
        else {
            wid_or_len[cnt / wl[1]][cnt % wl[1]] = 1;
            piece_of_paper(cnt + 1);

            wid_or_len[cnt / wl[1]][cnt % wl[1]] = 2;
            piece_of_paper(cnt + 1);
        }
    }

    public static int find_max_score() {
        int idx_i, idx_j;
        int num;
        int result = 0;

        for (int i = 0; i < wl[0]; i++) {
            for (int j = 0; j < wl[1]; j++) {

                idx_i = i;
                idx_j = j;
                num = 0;

                if (wid_or_len[idx_i][idx_j] == 1) {
                    while (wid_or_len[idx_i][idx_j] == 1 && visited[idx_i][idx_j] == false) {
                        num = num * 10 + info[idx_i][idx_j];
                        visited[idx_i][idx_j] = true;
                        idx_j++;
                        if (idx_j >= wl[1]) break;
                    }
                }
                else {
                    while (wid_or_len[idx_i][idx_j] == 2 && visited[idx_i][idx_j] == false) {
                        num = num * 10 + info[idx_i][idx_j];
                        visited[idx_i][idx_j] = true;
                        idx_i++;
                        if (idx_i >= wl[0]) break;
                    }
                }

                result += num;
            }
        }

        return result;
    }
}

코드 설명

각각의 종이 조각들은 가로 종이 조각이 될 수도, 세로 종이 조각이 될 수도 있다.
그래서 각각의 종이 조각들을 가로 종이 조각으로 세는 경우 한 번, 세로 종이 조각으로 세는 경우 한 번해서 총 두 번 연산에 참여하게 된다.

종이의 최대 크기는 $4\times4 = 16$

이 문제는 각각의 종이 조각들을 가로, 세로 종이 조각으로 구별하는 것 외에 구별된 내용을 가지고 연산을 해야하는 추가적인 프로시저가 필요한데 이를 위해 boolean 값을 갖는 visited 배열을 추가로 선언했다.

이 추가적인 프로시저에서는 16번을 순회를 하는데 이미 값에 영향을 준 인덱스를 참조할 경우 visited가 true로 되어 있어 연산에 중복 참여하지 않도록 제어해주었다.

while 문을 사용하는 방법도 있었는데 이럴 경우 인덱싱이 너무 복잡해지기 때문에 이중 for문을 사용하고 idx_i, idx_j 변수를 두어 이중 for문의 변수인 i, j와 독립적으로 움직이도록 했다.
연산에 참여하면 visited[idx_i][idx_j]를 true로 변경하고 종이 조각이 가로 종이 조각(이 경우 wid_or_len이 1값)일 경우 idx_j를 증가시켰고, 세로 종이 조각(이 경우 wid_or_len이 0값)일 경우 idx_i를 증가시켰다.

그리고, 백트래킹 함수의 종료 조건인 cnt == wl[0] * wl[1]이 되면 마지막 연산을 하는 함수가 호출되게 되는데 이 때 visited 함수를 변경시키므로 함수를 호출하기 전에 visited 배열을 모두 false로 초기화하는 과정을 거치게 했다. 이 초기화를 하는 과정에서 계속 오류가 발생했는데 Arrays.fill(visited, false)로만 썼더니 이중 배열을 한 번에 초기화시키지 못하기 때문에 발생한 것이었다. 이중 배열일 경우 for문으로 이차원부분을 순회하면서 Arrays.fill을 써야 한다.