[BOJ] 14391번 종이 조각 (Java/DFS)

문제

백준 14391번 종이 조각

---

풀이

1. DFS를 통해 check 배열에 가로, 세로를 표시합니다.
2. 가로로 이어지는 숫자는 true, 세로로 이어지는 숫자는 false 입니다.
3. check 배열을 전부 탐색하면 getSum 함수를 호출해 각 경우의 합의 구합니다.
4. 최대 합과 비교하여 값을 갱신합니다.

소스 코드

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

public class Main {

	static int N, M, arr[][];
	static boolean check[][];
	static int res;

	public static void main(String[] args) throws Exception {
		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];
		check = new boolean[N][M]; // 가로, 세로를 체크하기 위한 배열
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < M; j++) {
				arr[i][j] = temp.charAt(j) - '0';
			}
		} // input end

		res = 0;
		set(0, 0);
		System.out.println(res);
	}

	private static void getSum() {
		int sum = 0;

		for (int i = 0; i < N; i++) {
			int temp = 0;
			for (int j = 0; j < M; j++) {
				if (check[i][j] == true) {
					temp *= 10;
					temp += arr[i][j];
				} else {
					sum += temp;
					temp = 0;
				}
			}
			sum += temp;
		}

		for (int j = 0; j < M; j++) {
			int temp = 0;
			for (int i = 0; i < N; i++) {
				if (check[i][j] == false) {
					temp *= 10;
					temp += arr[i][j];
				} else {
					sum += temp;
					temp = 0;
				}
			}
			sum += temp;
		}

		res = Math.max(res, sum);
	}

	private static void set(int x, int y) {

		if (x >= N) { // 마지막 행까지 다 셋팅하면 합 구하기
			getSum();
			return;
		}

		if (y >= M) {
			set(x + 1, 0);
			return;
		}

		check[x][y] = true; // 가로
		set(x, y + 1);

		check[x][y] = false; // 세로
		set(x, y + 1);
	}

}

---