출처
https://www.acmicpc.net/problem/14391
문제
종이를 직사각형으로 적절하게 잘라 숫자를 얻을 수 있는데 그 합계가 가장 큰 경우의 합계를 구하는 문제이다.
풀이
이런 문제는 역시 방법이 없다. 완전 탐색을 통해 모든 경우의 수를 살펴보아야 한다.
이 문제에서 숫자를 얻을 수 있는것은 다음과 같이 세개의 경우가 있다.
- 자기 자신만 자르는 경우 (단일 숫자)
- 옆으로 한칸 포함하여 자르는 경우
- 아래로 한칸 포함하여 자르는 경우
이 세가지 경우를 모두 탐색 가능하도록 DFS로 구현해 보겠다.
DFS
먼저 DFS의 인자는 네개이다.
public static void dfs(int x, int y, int num, int sum)현재 종이를 잘라 만들어진 숫자인 num, 현재까지 구한 숫자들의 합을 저장하는 sum, 현재 탐색이 진행중인 위치인 x y 정보를 변수로 받는다.
재귀함수이기 때문에 종료조건을 미리 설정해주도록 하겠다.
if (x == N-1 && y == M-1) {
answer = Math.max(sum, answer);
if (answer == 0) {
answer = map[0][0];
}
return;
}X와 Y가 모두 종료 지점에 도착하였을때 종료한다. 현재까지 합을 저장한 sum과 정답인 answer을 Math.max로 비교하여 최대값을 저장해둔다. 아래 if문의 경우는, 원소가 하나인 경우 동작하지 않는 예외를 처리하기 위해 작성하였다.
이후 visited 배열을 통해 관리되고 있는 방문 현황을 통해, 만약 방문한 탐색지점이라면 아무것도 하지 않고 다음 DFS를 호출한다.
만약 방문하지 않았다면, 아래와 같이 작동한다.
else {
visited[x][y] = true;
num = num * 10 + map[x][y];
//본인까지 자르기
toNext(x, y, 0, sum + num);첫번째 경우인 본인만 자르는 경우에 해당한다.
toNext() 함수는, 열에 1씩 더해서 탐색을 진행하다가 다음 행으로 넘어가는 경우를 대비해 처리하도록 한 함수이다.
public static void toNext(int x, int y, int num, int sum) {
if (isRange(x, y+1)) { // 다음 행으로 넘어가지 않음
dfs(x, y+1, num, sum);
} else if (isRange(x+1, 0)){ //다음 행으로 넘어감
dfs(x+1, 0, num, sum);
} else {
dfs(N-1, M-1, num, sum); // 마지막 지점에서 toNext() 호출시
// 행을 바꾸지 않고 마지막 지점 호출
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}옆으로 한칸 포함하여 자르는 경우
//오른쪽 합쳐서 자르기
tmp = num;
for (i = y + 1; i < M; i++) {
if (visited[x][i]) {
break;
}
visited[x][i] = true;
tmp = tmp * 10 + map[x][i];
toNext(x, i, 0, sum + tmp); // 여기서 i인 이유는 가로로 i칸을 잘랐으니
//그 이후로 이동해야 하기 때문
}
for (int j = y + 1; j < i; j++) {
visited[x][j] = false;
}오른쪽으로 한칸 포함해서 자르는 경우의 코드이다. 오른쪽으로는 종이 끝까지 자를 수 있기 때문에 for문으로 DFS를 호출한다.
만약 한칸씩 자르다가 방문한 지점이 나오면 더이상 자를 수 없으므로 탐색은 종료된다.
이때 i와 tmp의 값을 지역변수로 설정하였다. i는 가로로 자르는 DFS를 모두 진행한 후 다시 visited를 false로 바꾸기 위해 사용하였다. (i까지 되돌리는 것이 아닌, 끝까지 되돌리게 된다면 현재 단계에서 자르지 않아도 false 처리가 되어 오류 발생 가능)
tmp는 현재 탐색지점 까지의 잘라진 종이의 값인 num을 저장하고 있다가, for문 내에서 계속 잘라진 종이를 추가한 값의 상태를 담고있도록 하였다.
자를때 마다 다음 위치의 DFS를 호출한다. 다음 DFS를 호출한다는 것은 현재 방향의 종이를 지금까지 포함시킨 값까지 자르고 넘어간다는 것을 의미한다. 따라서 sum에 num을 더해주고 num을 초기화 한다.
아래로 한칸 포함하여 자르는 경우
//아래 합쳐서 자르기
int i, tmp = num;
for (i = x + 1; i < N; i++) {
if (visited[i][y]) {
break;
}
visited[i][y] = true;
tmp = tmp * 10 + map[i][y];
toNext(x, y, 0, sum + tmp);
}
for (int j = x + 1; j < i; j++) {
visited[j][y] = false;
}모든 경우로 잘라보고, 마지막으로 탐색 지점의 위치를 false로 초기화 해주며 dfs를 종료한다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] map;
static int answer;
static int N, M;
static boolean[][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
visited = new boolean[N][M];
answer = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), "");
String str = st.nextToken();
for (int j = 0; j < M; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
dfs(0, 0, 0, 0);
bw.write(answer + "\n");
br.close();
bw.flush();
bw.close();
}
public static void dfs(int x, int y, int num, int sum) {
if (x == N-1 && y == M-1) {
answer = Math.max(sum, answer);
if (answer == 0) {
answer = map[0][0];
}
return;
}
if (visited[x][y]) {
toNext(x, y, num, sum);
} else {
visited[x][y] = true;
num = num * 10 + map[x][y];
//본인까지 자르기
toNext(x, y, 0, sum + num);
//아래 합쳐서 자르기
int i, tmp = num;
for (i = x + 1; i < N; i++) {
if (visited[i][y]) {
break;
}
visited[i][y] = true;
tmp = tmp * 10 + map[i][y];
toNext(x, y, 0, sum + tmp);
}
for (int j = x + 1; j < i; j++) {
visited[j][y] = false;
}
//오른쪽 합쳐서 자르기
tmp = num;
for (i = y + 1; i < M; i++) {
if (visited[x][i]) {
break;
}
visited[x][i] = true;
tmp = tmp * 10 + map[x][i];
toNext(x, i, 0, sum + tmp);
}
for (int j = y + 1; j < i; j++) {
visited[x][j] = false;
}
visited[x][y] = false;
}
}
public static void toNext(int x, int y, int num, int sum) {
if (isRange(x, y+1)) {
dfs(x, y+1, num, sum);
} else if (isRange(x+1, 0)){
dfs(x+1, 0, num, sum);
} else {
dfs(N-1, M-1, num, sum);
}
}
public static boolean isRange(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
}