Inor

[백준] 1992번 쿼드트리 본문

Algorithm/백준

[백준] 1992번 쿼드트리

Inor 2018. 1. 28. 01:13

- 문제 : https://www.acmicpc.net/problem/1992


 쿼드트리를 이용해서 4등분된 영역을 압축하는 알고리즘 문제 입니다.




- 풀이


 처음에는 괄호와 0, 1 값들을 스택에 넣어두고 pop 하면서 압축을 검사하고 다시 스택에 넣는 방법으로 풀려고 했지만 실패했습니다. 애초에 조금 돌아가는 방법으로 판단했고 분할/정복 방식으로 재귀호출하여 문제를 해결했습니다. 이 문제를 풀기에 앞서서 분할 정복에대한 개념을 잡고자 Merge Sort를 공부 했습니다.

 그리고 분할/정복 방식의 문제 풀이는 분할이 안될때까지 분할하고 정복(문제를 해결)하면서 문제를 풀어가는 방법과 분할 하기 전에 정복할 수 있는지 확인하고 다음 분할로 넘어가는 방식이 있는데 저는 분할을 하기 전에 정복할 수 있는지 확인하고 분할하도록 했습니다.

 4개의 영역(좌상, 우상, 좌하, 우하)에서 압축이 가능한지 확인하고 압축이 가능하다면 압축할 수 있는 번호를 반환하도록 했습니다. 그리고 압축이 불가능하다면 해당 영역을 다시 4 분할 했고 압축을 확인하는 과정을 반복했습니다.




- 코드

package implementation;

import java.util.Scanner;

public class QuadTree {
	Scanner sc;
	int n;
	int[][] map;
	String result;

	public void setValue() {
		String tStr;
		char[] values;
		sc = new Scanner(System.in);
		result = "";
		n = sc.nextInt();
		sc.nextLine();
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			tStr = sc.nextLine();
			values = tStr.toCharArray();
			for (int j = 0; j < n; j++) {
				map[i][j] = (int) (values[j] - '0');
			}
		}
	}

	public String dividConquer(int sRow, int sCol, int eRow, int eCol) {
		String upLeft, upRight, downLeft, downRight;
		if (eRow - sRow <= 0) {
			return map[sRow][sCol] + "";
		}
		
		// 좌상
		upLeft = dividConquer(sRow, sCol, (sRow + eRow) / 2, (sCol + eCol) / 2);
		// 우상
		upRight = dividConquer(sRow, (sCol + eCol) / 2 + 1, (sRow + eRow) / 2, eCol);
		// 좌하
		downLeft = dividConquer((sRow + eRow) / 2 + 1, sCol, eRow, (sCol + eCol) / 2);
		// 우하
		downRight = dividConquer((sRow + eRow) / 2 + 1, (sCol + eCol) / 2 + 1, eRow, eCol);
		
		if(upLeft.length() == 1 && upLeft.equals(upRight) && upRight.equals(downLeft) && downLeft.equals(downRight)){
			return upLeft;
		}else{
			return "(" + upLeft + upRight + downLeft + downRight + ")";
		}
	}

	public void solve() {
		setValue();
		System.out.println(dividConquer(0, 0, n - 1, n - 1));
	}

	public static void main(String[] args) {
		QuadTree m = new QuadTree();
		m.solve();
	}

}

'Algorithm > 백준' 카테고리의 다른 글

[백준] 10798번 세로읽기  (0) 2018.01.31
[백준] 12761번 돌다리  (0) 2018.01.31
[백준] 2573번 빙산  (0) 2018.01.12
[백준] 1963번 킹  (0) 2018.01.11
[백준] 1932번 숫자 삼각형  (0) 2018.01.10
Comments