[BAEKJOON_14391 - JAVA] 종이 조각

문제

www.acmicpc.net/problem/14391

14391번: 종이 조각

 

 

풀이

• 가로 세로를 어떻게 나눌지에 대해 매우 막막했다. 고민 뒤 다른분들의 코드를 참고
• 맵을 만들어 '1'과'0'으로 가로, 세로를 판단.
  ex) '1' 이면 가로, '0'이면 세로
  
  

• 주황색을 '1' / 파랑색을 '0' 이라고 가정하는 경우
  가로의 수 = 543 + 829 (3자리의수 2개) / 세로의수 = 9+2+7 (1자리의수 3개)로 판단 할 수 있다.
• 이와 같은 가정을 가지고 과정을 시작한다.

 

과정

1. dfs로 탐색 (row, col).
2. 가로 숫자 = true, 세로 숫자 = false 활용.
3. 열을 이동하며 가로,세로를 체크('true' or 'false').
4. 해당 행의 모든열을 체크한 경우 다음 행을 재귀 호출. 
5. 기저 조건 (모든 맵을 탐색한 경우) 만들어진 수를 계산.
6. 세로와 가로의 덧셈을 할때, 수의 자리(1의 자리 or 10의 자리) 신경을 쓴다.
7. 최댓값과 비교후 갱신.

 

 

알고리즘 지식

• BruteForce

 

 

JAVA코드

package BaekJoon_2020_12_22__23;

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

/**
 * @packageName : BaekJoon_2020_12_22
 * @fileName : BJ_14391_종이조각.java
 * @author : Mingeon
 * @date : 2020. 12. 23.
 * @language : JAVA
 * @classification : BruteForce
 * @time_limit : 2sec
 * @required_time : 02:00 ~ 05:55
 * @submissions : 1
 * @description
 */

public class BJ_14391_종이조각 {

	static int N; // 세로
	static int M; // 가로
	static int[][] map; // 수를 입력할 종이
	static boolean[][] visited; // 방문 관리
	static int maxVal; // 최댓값

	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());
		map = new int[N][M];
		visited = new boolean[N][M];
		maxVal = 0;

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

		dfs(0, 0);
		System.out.println(maxVal);

	}

	private static void dfs(int row, int col) {
		// 탐색 종료
		if (row >= N) {
			sum();
			return;
		}

		// 하나의 행의 체크 종료 -> 다음 행으로 이동
		if (col >= M) {
			dfs(row + 1, 0);
			return;
		}

		// 가로 숫자로 사용
		visited[row][col] = true;
		dfs(row, col + 1);

		// 세로 숫자로 사용
		visited[row][col] = false;
		dfs(row, col + 1);

	}

	private static void sum() {
		int ret = 0;
		int temp = 0;

		// 가로 숫자 계산
		for (int i = 0; i < N; i++) {
			temp = 0;
			for (int j = 0; j < M; j++) {
				// 가로 덧셈 -> true인 경우
				if (visited[i][j]) {
					temp *= 10; // 자릿수 이동 ex) 1 -> 10
					temp += map[i][j]; // ex) 10 -> 13
				} else {
					ret += temp;
					temp = 0; // temp 변수 초기화
				}
			}

			ret += temp;
		}

		// 세로 숫자 계산
		for (int i = 0; i < M; i++) {
			temp = 0;
			for (int j = 0; j < N; j++) {
				// 세로 덧셈 -> false인 경우
				if (!visited[j][i]) {
					temp *= 10; // 자릿수 이동 ex) 1 -> 10
					temp += map[j][i]; // ex) 10 -> 13
				} else {
					ret += temp;
					temp = 0; // temp 변수 초기화
				}
			}
			ret += temp;
		}
		maxVal = Math.max(maxVal, ret);

	}

}