백준 1992번 <쿼드 트리>

백준 알고리즘 1992번

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

---

1992번

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

 

입력으로 첫 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. 둘째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

 

출력으로 압축된 결과를 출력하면 된다.

---

문제 해결

재귀함수를 구현하여 풀었다.

isSame 함수는 x좌표, y좌표, 부분 배열의 크기, 전체 배열을 인자로 갖는다.

isSame(x, y, len, map)

• len이 1이라면 map[x][y]를 문자열로 바꿔서 반환한다. (부분 배열에 속하는 원소가 1개이기 때문에)
• 모두 같은지 확인해야 할 때 사용하는 int 형 변수 num에 map[x][y]를 저장해두고 boolean 변수 chk를 true로 설정한다.
• 세로는 x좌표부터 len개, 가로는 y좌표부터 len개를 보면서 num과 같지 않다면 chk를 false로 만들어주고 이중 for문을 빠져나온다.
• chk가 true라면 → 부분 배열의 원소가 모두 같다.
  • StringBuffer에 num을 넣는다.
• chk가 false라면 → 부분 배열의 원소가 다르다.
  • 해당 부분 배열의 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 isSame 함수를 재귀적으로 호출한다.
  • 이때 반환된 문자열의 길이가 1이라면 해당 문자열을 StringBuffer에 넣는다.
  • 반환된 문자열의 길이가 1보다 크다면 (해당 문자열)을 StringBuffer에 넣는다.
• StringBuffer에 있는 문자열을 최종적으로 반환한다.

main 함수에서 isSame의 반환값의 길이가 1이라면 그냥 출력하고 그렇지 않다면 괄호를 씌워서 출력한다.

(처음에 이 부분을 하지 않고 그냥 냈더니 80%쯤에서 틀렸습니다가 떴다.)

 

---

코드

package bj1992;

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[][] map = new int[n][n];
		for (int i = 0; i < n; i++) {
			String temp = br.readLine();
			for (int j = 0; j < n; j++) {
				map[i][j] = temp.charAt(j) - '0';
			}
		}
		String answer = isSame(0, 0, n, map);
		if (answer.length() == 1) {
			System.out.println(answer);
		} else {
			System.out.println("(" + answer + ")");
		}
	}

	public static String isSame(int x, int y, int len, int[][] map) {
		StringBuffer sb = new StringBuffer();

		if (len == 1) {
			sb.append(map[x][y]);
			return sb.toString();
		}
		int num = map[x][y];
		boolean chk = true;
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (map[x + i][y + j] != num) {
					chk = false;
					break;
				}
			}
			if (!chk)
				break;
		}
		if (chk) {
			sb.append(num);
		} else {
			int[] dx = { 0, 0, len / 2, len / 2 };
			int[] dy = { 0, len / 2, 0, len / 2 };
			for (int i = 0; i < 4; i++) {
				String temp = isSame(x + dx[i], y + dy[i], len / 2, map);
				if (temp.length() == 1) {
					sb.append(temp);
				} else {
					sb.append("(");
					sb.append(temp);
					sb.append(")");
				}
			}
		}
		return sb.toString();
	}

}

---

결과

---