문제
https://www.acmicpc.net/problem/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
접근
이 문제는 예전에도 스터디에서 풀었어야 했던 문제였는데, 당시에 그냥
'가로로 쭉 자르거나 세로로 쭉 자르거나 둘 중 하나 아닌가?'
이렇게 1차원적으로만 생각해서 풀었다가 대차게 틀린 후 영원히 방치해 두고 있었다....^^
이번에 다른 스터디원 분이 다시 한 번 풀어보자고 하셔서 재도전을 해보았다.
이 문제는 N과 M이 최대 4로 매우 작기 때문에 브루트포스로 풀 수 있다.
일단 내가 단순하게 생각했던 대로 가로로 쭉 자르거나 세로로 쭉 자르는 경우가 보통은 최대가 된다. 더해지는 숫자의 자릿수가 클수록 누적 합이 커지는 것은 자명하기 때문.
하지만, 역시 항상 그렇지만은 않다는 점이 문제이다.
4 4
1000
0001
0000
1000
위와 같이 가로나 세로로 쭉 잘랐을 때 0으로 시작하는 숫자가 존재하는 경우에는 이렇게 접근하는 것이 최댓값을 보장하지 않을 수 있다.
위 숫자들을 가로로만 자르면 1000 + 1 + 0 + 1000 = 2001,
세로로만 자르면 1001 + 0 + 0 + 100 = 1101이 나온다.
하지만, [0][0]부터 [0][3]에서 1000을 취하고, [3][0]부터 [3][3]에서 1000을 취하고, [1][3]부터 [2][3]에서 10을 취해서 모두 더하면 2001보다 큰 2010이 나오게 된다.
따라서, 이런 경우에는 직접 해보는 수밖에 없다! 말 그대로 브루트포스.
숫자는 항상 왼쪽에서 오른쪽, 혹은 위쪽에서 아래쪽으로만 읽기 때문에 가로나 세로로 쭉 잘랐을 때 0으로 시작하는 숫자가 존재하는 경우는 row 값 또는 column 값 중 하나 이상이 0인 경우이다. 따라서 나는 이런 케이스에 대해서만 브루트포스를 적용해줬고, 일반적인 경우에는 이전에 했던 것처럼 가로로 쭉 찢고 세로로 쭉 찢어 두 값을 비교하는 방식을 사용했다.
구현
import java.io.*;
class Main {
static int maxScore = 0;
static int N;
static int M;
static int[][] paper;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
paper = new int[N][M];
visited = new boolean[N][M];
boolean hasZero = false;
for (int i = 0; i < N; i++) {
String row = br.readLine();
for (int j = 0; j < M; j++) {
paper[i][j] = Integer.parseInt(row.substring(j, j + 1));
if (paper[i][j] == 0 && (i == 0 || j == 0)) {
hasZero = true;
}
}
}
if (hasZero) {
findMaxScore(0);
} else {
if (N < M) {
maxScore = cutHorizontally();
} else if (N > M) {
maxScore = cutVertically();
} else {
maxScore = Math.max(cutHorizontally(), cutVertically());
}
}
System.out.println(maxScore);
}
private static void findMaxScore(int currScore) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (paper[row][col] == 0 || visited[row][col]) {
continue;
}
// paper[row][col]부터 시작해 세로로 자르기
int temp = 0;
int idx = row;
for (; idx < N && !visited[idx][col]; idx++) {
visited[idx][col] = true;
temp = temp * 10 + paper[idx][col];
findMaxScore(currScore + temp);
}
for (--idx ; idx >= row + 1; idx--) {
visited[idx][col] = false;
}
// paper[row][col]부터 시작해 가로로 자르기
temp = paper[row][col];
idx = col + 1;
for (; idx < M && !visited[row][idx]; idx++) {
visited[row][idx] = true;
temp = temp * 10 + paper[row][idx];
findMaxScore(currScore + temp);
}
for (--idx; idx >= col; idx--) {
visited[row][idx] = false;
}
return;
}
}
maxScore = Math.max(maxScore, currScore);
}
private static int cutHorizontally() {
int sum = 0;
for (int row = 0; row < N; row++) {
int temp = 0;
for (int col = 0; col < M; col++) {
temp = temp * 10 + paper[row][col];
}
sum += temp;
}
return sum;
}
private static int cutVertically() {
int sum = 0;
for (int col = 0; col < M; col++) {
int temp = 0;
for (int row = 0; row < N; row++) {
temp = temp * 10 + paper[row][col];
}
sum += temp;
}
return sum;
}
}다른 부분은 앞서 설명한 내용과 같기 때문에 브루트포스를 수행하는 함수인 findMaxScore()만 자세히 보겠다.
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (paper[row][col] == 0 || visited[row][col]) {
continue;
}
}
}
종이에 적힌 숫자들을 순회하면서 아직 방문하지 않은 숫자를 찾는다.
그렇게 찾은 숫자가 가장 높은 자릿수가 되도록 종이를 자를 것이다.
가장 높은 자릿수가 0인 건 더해도 의미가 없기 때문에 그냥 스킵했다.
아직 방문하지 않은 0이 아닌 숫자를 찾았다면, 이 숫자를 시작으로 해서 세로로 자르거나, 가로로 자를 수 있을 것이다.
int temp = 0;
int idx = row;
for (; idx < N && !visited[idx][col]; idx++) {
visited[idx][col] = true;
temp = temp * 10 + paper[idx][col];
findMaxScore(currScore + temp);
}
for (--idx ; idx >= row + 1; idx--) {
visited[idx][col] = false;
}먼저 세로로 자르기 위해서 col 값은 고정해 놓고, row 값만 1씩 증가시켰다. 종이 끝(N - 1)까지 잘라서 더 이상 row 값을 증가시킬 수 없거나, 이미 잘라진 종이에 도달할 때까지 (visited[idx][col]가 true가 될 때까지).
(row, col) 위치에서 시작해서 자릿수를 하나씩 늘려 나가며 종이를 자르고, 그렇게 잘린 종이 조각이 나타내는 수는 temp에 저장했다. 종이를 자른 후 재귀 호출을 통해 다음 종이 조각을 자르는 과정을 반복했다.
재귀 호출이 끝났다는 것은 (row, col)로 시작해서 가로로 자르는 경우를 모두 탐색했다는 뜻이다. 따라서 visited 배열의 값을 다시 false로 바꿔줬다.
temp = paper[row][col];
idx = col + 1;
for (; idx < M && !visited[row][idx]; idx++) {
visited[row][idx] = true;
temp = temp * 10 + paper[row][idx];
findMaxScore(currScore + temp);
}
for (--idx; idx >= col; idx--) {
visited[row][idx] = false;
}가로로 자르는 것도 세로로 자르는 것과 과정은 똑같다.
row 값을 고정해 놓고 col 값만 1씩 증가시키면 된다.
여기서는 col가 아닌 col + 1부터 탐색하는 이유는, (row, col) 한 자릿수로 자르는 경우는 이미 세로로 자르면서 탐색을 끝냈기에 두 자릿수로 자르는 경우부터 탐색하면 되기 때문이다.
private static void findMaxScore(int currScore) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
if (paper[row][col] == 0 || visited[row][col]) {
continue;
}
// 중략
return;
}
}
maxScore = Math.max(maxScore, currScore);
}이렇게 (row, col)로 시작하도록 종이를 자르는 경우에 대해 탐색이 모두 끝났으면 함수를 종료하면 된다.
어차피 재귀 호출을 통해 다른 위치에서 시작하는 경우도 탐색이 되기 때문에 종료하지 않으면 탐색을 중복해서 하게 된다.
다 잘 구현해 두고 이걸 생각 못해서 시간 초과 때문에 애먹었다....
이중 for문을 모두 순회했음에도 함수가 종료되지 않았다는 것은 모든 visited의 값이 true였다는 뜻이다. 즉, 모든 종이 조각을 방문했다는 뜻이므로 maxScore 값을 갱신한다.
