[백준] 1992. 쿼드트리 (자바 JAVA)

[ 문제 ]  [백준] 1992. 쿼드트리 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

 

---

# 접근 방법 및 풀이 

 

• 프로그래머스 쿼드압축과 비슷한 문제다. 프로그래머스때는 재귀를 이용하지 않고 풀었는데 이번엔 재귀를 이용했다.
  
  • https://ilmiodiario.tistory.com/118
• 먼저, quadTree() 재귀 메소드를 만들었다. 재귀에서 파라미터는 변하는 값이므로 int r, int c, int size로 했다.
• r행 c열부터 size까지 살펴보면서 숫자가 다 같다면 압축이 되고, 숫자가 다르면 압축이 되지 않는다.
• 따라서 압축이 되는지 안되는지 체크할 check()메소드를 만들었다.
• 만약 check( )가 true라면 정답을 담을 StringBuilder에 압축된 문자를 추가하고, false라면 "왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래"로 재귀를 탄다. 이때 size는 1/2로 나누어준다.
• 자세한건 코드참조

 

# 주의할 점 

 

• 천천히 로직대로 생각해보기

 

JAVA 코드

package Silver;

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

public class bj1992_쿼드트리 {
	static int N;
	static String map[][];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		map = new String[N][N];
		for (int i = 0; i < N; i++) {
			String s = in.readLine();
			map[i] = s.split("");
		}
		quadTree(0, 0, N);
		System.out.println(sb.toString());
	}
	
	private static void quadTree(int r, int c, int size) {
		
		if(check(r, c, size)) {
			sb.append(map[r][c]);
			return;
		}
		int newSize = size/2;
		sb.append("(");
		quadTree(r, c, newSize);//왼쪽위
		quadTree(r, c+newSize, newSize);//오른쪽 위
		quadTree(r+newSize, c, newSize);//왼쪽 아래
		quadTree(r+newSize, c+newSize, newSize);//오른쪽 아래
		sb.append(")");
	}

	private static boolean check(int r, int c, int size) {
		for (int i = r; i < r+size; i++) {
			for (int j = c; j < c+size; j++) {
				if(!map[i][j].equals(map[r][c]))
					return false;
			}
		}
		return true;
	}
}

 

 

 

REVIEW

재귀 많이 풀자...