[백준] 14391번 : 종이 조각 Gold3(골드3) - JAVA[자바]

[Gold III] 종이 조각 - 14391

문제 링크

성능 요약

메모리: 17160 KB, 시간: 88 ms

분류

비트마스킹, 브루트포스 알고리즘

제출 일자

2024년 6월 19일 15:48:05

문제 설명

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 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. 이미 사용된 종이라면(visit = true) 넘어간다.

3. 만약 사용된 종이가 아니라면(visit = false) 자를 수 있을만큼 세로와 가로를 잘라주고 넘어간다.

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

/**
 * 문제: BOJ_14391_종이 조각
 * 메모리: 17160KB
 * 시간: 88ms
 * 접근 방법
 * 1. 백트래킹을 이용하여 각 종이에 대해서 처리한다.
 * 2. 이미 사용된 종이라면(visit = true) 넘어간다.
 * 3. 만약 사용된 종이가 아니라면(visit = false) 자를 수 있을 만큼 세로와 가로를 잘라주고 넘어간다.
 */
public class Main {
    static int[][] map;
    static boolean[][] visit;
    static int N, M, answer;

    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());
        map = new int[N][M];
        visit = new boolean[N][M];

        // Input
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        } // Input End

        solve(0, 0, 0);
        System.out.println(answer);
    }

    private static void solve(int x, int y, int value) {
        // 모든 확인시 최대값 갱신 후 종료
        if (x == N) {
            answer = Math.max(answer, value);
            return;
        }
        // y의 끝값이라면 다음 행을 확인
        if (y == M) {
            solve(x + 1, 0, value);
            return;
        }
        // 이미 방문했다면 넘어간다.
        if (visit[x][y]) {
            solve(x, y + 1, value);
            return;
        }

        int tmp = map[x][y];
        visit[x][y] = true;
        solve(x, y + 1, value + tmp);
        visit[x][y] = false;

        // 가로 확인
        int i = 1;
        for (; x + i < N; i++) {
            int nX = x + i;
            if (visit[nX][y]) break;

            tmp *= 10;
            tmp += map[nX][y];
            visit[nX][y] = true;
            solve(x, y + 1, value + tmp);
        }
        for (int j = 1; j < i; j++) visit[x + j][y] = false;

        tmp = map[x][y];
        i = 1;
        for (; y + i < M; i++) {
            int nY = y + i;
            if (visit[x][nY]) break;

            tmp *= 10;
            tmp += map[x][nY];
            visit[x][nY] = true;
            solve(x, y + 1, value + tmp);
        }
        for (int j = 1; j < i; j++) visit[x][y + j] = false;
    }
}