[Java] 백준 14391번: 종이 조각 - Brute Force, DFS

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까지 중 하나이다.

출력

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

 

---

 

 

가로, 세로를 어떻게 잘라야 할 지 막막했던 문제..

완전탐색 dfs를 이용했다.

 

depth로 깊이를 구해서 n*m일 때까지 dfs를 돌릴 것이다.

그리고 그때마다 계산한 값을 sum에 더해주면 최댓값을 구해주면 된다.

public static void dfs(int depth, int sum){
    if(depth == n*m){
        answer = Math.max(sum, answer);
        return;
    }

 

x, y의 값은 m으로 나눈 몫과 나머지로 구할 수 있다.

int x = depth / m;
int y = depth % m;

 

이미 방문했다면 카운트만 해주고 sum은 바로 넘겨준다.

if(visit[x][y])
    dfs(depth+1, sum);

 

방문을 안한 경우 3가지로 나누어서 구한다.

1. 현재 위치 계산

2. 세로로 자르는 경우

3. 가로로 자르는 경우

 

1. 현재 위치 계산

int num = 0;
visit[x][y] = true;
num = num*10 + arr[x][y];
dfs(depth+1, sum+num);

 

2. 세로로 자르는 경우

- 1에서 계산했던 값을 temp로 넘겨준다. (이후 가로 계산에서도 써야하기 때문)

- 현재의 위치가 1의 자리수로 더해지기 때문에 이전의 값은 10을 곱해준다.

ex) 12 에서 현재의 값이 3일 때 12*10 + 3 = 123 으로 구할 수 있다.

int i, temp = num;
for(i=x+1; i<n; i++){
    if(visit[i][y])
        break;
    visit[i][y] = true;
    temp = temp*10 + arr[i][y];
    dfs(depth+1, sum+temp);
}

for(int j=x+1; j<i; j++)
    visit[j][y] = false;

 

3. 가로로 자르는 경우

- 세로에서 x, y 위치만 바꿔서 똑같이 해주면 된다.

dfs(depth+i-y+1,sum+temp); 에서 depth+i-y+1 을 하는 이유는 ??
가로로 자르기 때문에 현재 조각이 차지하는 모든 칸을 건너 뛰고 다음 탐색 시점으로 이동하기 위함이다.
(세로는 아래로 한 칸씩 이동하므로 1씩 증가시킨다.)

temp = num;
for(i=y+1; i<m; i++){
    if(visit[x][i])
        break;
    visit[x][i] = true;
    temp = temp*10 + arr[x][i];
    dfs(depth+i-y+1, sum+temp);
}

for(int j=y+1; j<i; j++)
    visit[x][j] = false;

//현재 위치도 되돌리기
visit[x][y] = false;

 

 

소스 코드

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

public class Main {
	static int n, m;
	static int[][] arr;
	static boolean[][] visit;
	static int answer = 0;

	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());
		arr = new int[n][m];
		visit = new boolean[n][m];

		for(int i=0; i<n; i++){
			String str = br.readLine();
			for(int j=0; j<m; j++){
				arr[i][j] = str.charAt(j) - '0';
			}
		}

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

	public static void dfs(int depth, int sum){
		if(depth == n*m){
			answer = Math.max(sum, answer);
			return;
		}

		int x = depth / m;
		int y = depth % m;

		if(visit[x][y])
			dfs(depth+1, sum);
		else {
			//현재 위치 계산
			int num = 0;
			visit[x][y] = true;
			num = arr[x][y];
			dfs(depth+1, sum+num);

			//세로로 자르는 경우
			int i, temp = num;
			for(i=x+1; i<n; i++){
				if(visit[i][y])
					break;
				visit[i][y] = true;
				temp = temp*10 + arr[i][y];
				dfs(depth+1, sum+temp);
			}

			for(int j=x+1; j<i; j++)
				visit[j][y] = false;

			//가로로 자르는 경우
			temp = num;
			for(i=y+1; i<m; i++){
				if(visit[x][i])
					break;
				visit[x][i] = true;
				temp = temp*10 + arr[x][i];
				dfs(depth+i-y+1, sum+temp);
			}

			for(int j=y+1; j<i; j++)
				visit[x][j] = false;

			//현재 위치도 되돌리기
			visit[x][y] = false;
		}
	}
}