[백준/BOJ] 14391번 종이 조각 자바 풀이

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를 사용했다.

비트마스킹으로도 풀 수 있는데, 나한테는 아직 익숙치가 않아서 일반적인 DFS로 풀었다.

(알고보니 예전에 다른 분 풀이를 참고해서 비트마스킹으로 문제를 풀었었는데, 그때보다 지금이 시간이 더 적게 나왔다...;;)

 

 

 

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		p = new int[N][M];
		visit = new boolean[N][M];

		for(int i=0;i<N;i++) {
			String input = br.readLine();
			for(int j=0;j<M;j++)
				p[i][j] = input.charAt(j) - '0';
		}
		
		DFS(0, 0, 0);

입력으로 주어진 N, M과 종이조각을 변수에 저장하고 DFS를 진행한다.

 

 

	static void DFS(int depth, int num, int sum)

DFS 메소드의 매개변수는 depth, num, sum이다.

depth를 통해 DFS를 종료할(return) 시점을 정하고, 접근할 배열의 행, 열 위치를 구한다.

num에는 종이를 자른 값을 저장한다. 한칸씩 더 자를 때마다 num을 갱신한다.

sum에는 종이를 그만 자르고자 할때, num값을 누적하여 더한다. 이때 sum에 더해준 num은 0이 되어야 한다. 

 

 

 

		int r = depth / M;
		int c = depth % M;

		if(visit[r][c]) {
			DFS(depth + 1, num, sum);
		}

매개변수로 전달받은 depth를 통해 배열의 행과 열을 구한다.

구한 배열의 위치를 이미 방문했다면,  아무것도 진행하지 않고 다음 DFS를 호출한다.

 

 

 

		else {
			visit[r][c] = true;
			num = num * 10 + p[r][c];
			DFS(depth + 1, 0, sum + num);

배열의 위치를 방문하지 않았다면 방문처리 한다.

 

먼저 종이를 자르는 경우는 아래의 세 가지 경우가 존재한다.

1) 자기자신만을 자르는 경우

2) 세로로 한칸 포함해서 자르는 경우

3) 가로로 한칸 포함해서 자르는 경우

 

num에 자기 자신만을 포함시키고 sum에 더해주므로 위 코드는 1)에 해당한다.

 

 

			int i, temp = num;
			for(i=r+1;i<N;i++) {
				if(visit[i][c])
					break;

				visit[i][c] = true;
				temp = temp * 10 + p[i][c];
				DFS(depth + 1, 0, sum + temp);
			}
			
			for(int j=r+1;j<i;j++)
				visit[j][c] = false;

2) 세로로 한칸 포함해서 자르는 경우의 코드이다.

세로로는 현재 위치에서 종이 가장 끝까지 자를 수 있다.

만약 한칸씩 자르다가 중간에 이미 방문처리 되어있는 종이를 발견한다면

더이상 자를 수 없으므로 세로로 자르는 for문을 벗어나온다.

 

이때 i를 (for문 안의 변수가 아닌) DFS 메소드의 지역변수로 선언해

세로로 자른 DFS를 모두 진행한 후 다시 방문처리를 되돌리는 데에 사용한다.

(만약 i 전까지 false로 되돌리는 것이 아닌 N까지 되돌린다면,

현재 단계에서 자른 종이가 아닌데도 false값으로 바꾸어 이상한 값이 도출될 수 있다.)

 

종이를 세로로 두칸, 세로로 세칸 여러가지로 자를 수 있으므로 자를 때마다 다음 위치의 DFS를 호출한다.

(다음 DFS를 호출한다는 것은 현재 방향의 종이를 지금까지 포함시킨 값들로 자른다는 것이므로

sum에 num을 더해주고 num은 0이 된다)

 

 

			temp = num;
			for(i=c+1;i<M;i++) {
				if(visit[r][i])
					break;
				visit[r][i] = true;
				temp = temp * 10 + p[r][i];
				DFS(depth + i - c + 1, 0, sum + temp);
			}

			for(int j=c+1;j<i;j++)
				visit[r][j] = false;

3) 가로로 한칸 포함해서 자르는 경우의 코드이다.

2) 코드는 r을 1씩 더해주며 세로로 종이를 포함시켰지만 3)은 c를 1씩 더해주며 가로로 종이를 포함시킨다.

 

 

 

			visit[r][c] = false;

현재 위치에서 자기자신만 자르기, 세로방향, 가로방향 모든 경우를 잘라봤다면 

마지막으로 현재위치의 방문처리를 되돌린다.

 

 

 

 

 

전체 코드

 

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

public class Main {
	static int N, M;
	static int[][] p;
	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());
		p = new int[N][M];
		visit = new boolean[N][M];

		for(int i=0;i<N;i++) {
			String input = br.readLine();
			for(int j=0;j<M;j++)
				p[i][j] = input.charAt(j) - '0';
		}
		
		DFS(0, 0, 0);
		System.out.println(answer);
	}

	static void DFS(int depth, int num, int sum) {
		if(depth == N*M) {
			answer = Math.max(sum, answer);
			return;
		}

		int r = depth / M;
		int c = depth % M;

		if(visit[r][c]) {
			DFS(depth + 1, num, sum);
		}
		else {
			visit[r][c] = true;
			num = num * 10 + p[r][c];
			DFS(depth + 1, 0, sum + num);

			int i, temp = num;
			for(i=r+1;i<N;i++) {
				if(visit[i][c])
					break;

				visit[i][c] = true;
				temp = temp * 10 + p[i][c];
				DFS(depth + 1, 0, sum + temp);
			}
			
			for(int j=r+1;j<i;j++)
				visit[j][c] = false;
			
			temp = num;
			for(i=c+1;i<M;i++) {
				if(visit[r][i])
					break;
				visit[r][i] = true;
				temp = temp * 10 + p[r][i];
				DFS(depth + i - c + 1, 0, sum + temp);
			}

			for(int j=c+1;j<i;j++)
				visit[r][j] = false;
			
			visit[r][c] = false;
		}
	}

}