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

 

[코드]

import java.util.*;

public class BaekJoon_14391 {
	static boolean[][] visited;
	static int[][] map;
	static int n,m,max=Integer.MIN_VALUE;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		visited=new boolean[n][m];
		
		for(int i=0;i<n;i++) {
			String str=sc.next();
			for(int j=0;j<m;j++) {
				map[i][j]=str.charAt(j)-'0';
			}
		}
		
		check(0,0);
		System.out.println(max);
	}
	
	/*
	 * 가로로 더해야 하는 숫자와, 세로로 더해야 하는 숫자를 각각 true/false로 나타내는 함수
	 * 각 배열의 값이 true일수 있는 경우와 false일 수 있는 경우가 있기 때문에 
	 * 모든 배열의 값이 이룰 수 있는 경우의 수를 백트래킹으로 탐색한다. 
	 */
	static void check(int r, int c) {
		// 마지막 행에 도달했다면 해당 경우의 가로, 세로합을 구한다.
		if(r>=n) {
			sum();
			return;
		}
		
		// 하나의 열이 true/false 표시가 완료됐다면 다음 행으로 넘어간다.
		if(c>=m) {
			check(r+1,0);
			return;
		}
		
		visited[r][c]=true; // 가로 숫자에 포함하고, 다음 열로 넘어간다.
		check(r,c+1);
		
		/*
		 * 여기서 다시 visied 배열을 값을 되돌리기 때문에 
		 * 각 경우마다 visited 배열을 초기화 해 줄 필요가 없다.
		 */
		visited[r][c]=false; // 세로 숫자에 포함하고, 다음 열로 넘어간다.
		check(r,c+1);
	}
	
	static void sum() {
		int sum=0; // 한 경우의 가로, 세로 숫자의 합
		
		// 가로 숫자 더하기
		for(int i=0;i<n;i++) {
			int temp=0;
			for(int j=0;j<m;j++) {
				// visited 값이 true인 경우는 가로 숫자에 해당
				if(visited[i][j]) {
					temp*=10; // 자릿수 밀기
					temp+=map[i][j]; // 해당 숫자 일의 자리에 더하기
				}
				/*
				 * visited 값이 false를 만난다면 세로 숫자에 해당하기 때문에 
				 * 이전까지 구해진 가로 숫자를 더하고 temp 초기화
				 */
				else {
					sum+=temp;
					temp=0;
				}
			}
			
			sum+=temp; // 한 행이 모두 가로숫자에 포함되는 수라면 여기서 더해주어야 한다.
		}
		
		// 세로 숫자 더하기
		for(int i=0;i<m;i++) {
			int temp=0;
			for(int j=0;j<n;j++) {
				// visited 값이 false인 경우는 세로 숫자에 해당
				if(!visited[j][i]) {
					temp*=10; // 자릿수 밀기
					temp+=map[j][i]; // 일의 자리에 더하기
				}
				/*
				 * visited 값이 true를 만난다면 가로 숫자에 해당하기 때문에 
				 * 이전까지 구해진 세로 숫자를 더하고 temp 초기화
				 */
				else {
					sum+=temp;
					temp=0;
				}
			}
			sum+=temp; // 한 열이 모두 세로숫자에 포함되는 수라면 여기서 더해주어야 한다.
		}
		
		max=Math.max(max, sum); // 최댓값 갱신
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용해 가능한 모든 경우의 수를 탐색하는 문제였다. 가로 숫자에 포함하는 수는 true로, 세로 숫자에 포함되는 수는 false로 boolean 배열에 표시해준다. 이때 현재 숫자를 가로 숫자에 포함 하느냐 아니냐의 두 가지 경우 밖에 없기 때문에 true 값으로 변경하고 재귀호출, false 값으로 다시 초기화 해주고 재귀호출 하면 매 경우마다 boolean 배열을 초기화 해줄 필요가 없다. 이때 열을 늘려주면서 재귀호출 해주다가 열의 값이 m과 같아지면 행을 1 늘려주고, 행이 n과 같아지면 해당 경우에서 가로 숫자와 세로 숫자의 합을 구해주고, 재귀호출을 종료해주면 된다. 

 처음에 가로 숫자와 세로 숫자의 합을 구해줄때 한 행, 한 열이 모두 가로 숫자, 세로 숫자일 경우를 생각해서 하나의 큰 for 문이 끝나기 전에 temp 값을 누적해주는 것을 놓쳐 오답 처리를 받았었다. 주의해야 할 부분인것 같다.