백준 1992

문제

---

2630 문제와 비슷 ( https://velog.io/@jhkim040/%EB%B0%B1%EC%A4%80-2630 )

차이점은 각 구역의 숫자 분포 상태를 모두 출력해야 하고, 분할마다 괄호를 추가해주어야 하는 점.

1) 4등분으로 분할을 하고, 만약 정복(같은 숫자만 존재)되었다면 해당 구역의 숫자를 출력

2) 다른 숫자가 존재하여 분할을 또 해야 한다면 괄호를 열고 분할을 시도

3) 끝나면 괄호 닫아주기

---

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class P1992 {

	static int[][] board;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		board = new int[N][N];

		String input;
		for(int i = 0; i < N; i++) {
			input = br.readLine();

			for(int j = 0; j < N; j++) {
				board[i][j] = input.charAt(j) - '0';  
			}
		}		
		partition(0, 0, N);
		
		bw.write(sb.toString());
		
		br.close();
		bw.flush();
		bw.close();
	}

	// 해당 구역이 모두 같은 숫자인지 확인
	private static boolean sameNumber(int row, int col, int size) {
		int value = board[row][col];

		for(int i = row; i < row + size; i++) {
			for(int j = col; j < col + size; j++) {
				if(board[i][j] != value) {
					return false;
				}
			}
		}
		return true;
	}
	
	private static void partition(int row, int col, int size) {
    	// 1) 해당 구역이 모두 같은 숫자 
		if(sameNumber(row, col, size)) {
			sb.append(board[row][col]);
			return;
		}
        
        // 2) 해당 구역에 다른 숫자 존재
		
		int nextSize = size / 2;
		
		sb.append('('); // 괄호 열고, 4분할해서 재귀 탐색
		
		partition(row, col, nextSize);
		partition(row, col + nextSize, nextSize);
		partition(row + nextSize, col, nextSize);
		partition(row + nextSize, col + nextSize, nextSize);
		
		sb.append(')'); // 탐색 끝나면 괄호 닫기
	}

}