3D 데이터를 표한하기 위한 자료구조를 "장면 그래프 (Scene Graph)" 라고한다.
"쿼드 트리"는 위의 자료구조에 포함된다.
백준 1992 번 문제를 풀면서 이해를 해보겠다.
3D 데이터를 표현한다
=> 사진의 흑백 도형이 3D 데이터이며 0이 백 흑이1인 상태를
(0(0011)(0(0111)01)1) 로 표현한다. 로 이해 했다.
쿼드트리 는 어떻게 적용하나?
=> 하나의 평면을 4개의 네모로 분할한다
하나의 네모 안이 0또는 1로 통일되면 0과 1로표기
그렇지 않으면 네모안을 4분의 1로 다시분 할한다
(이과정을 반복한다)
여기서는 분할시 () 안에 넣어주며
표현은 왼쪽위,오른쪽위,왼쪽아래
,오른쪽 아래이다
쿼드트리 형식으로 분할해보자
=> ( 0 ( ) ( ) 1 )
=> ( 0 ( 0 0 1 1 ) ( 0 ( ) 0 1 ) 1)
=> ( 0 ( 0 0 1 1 ) ( 0 ( 0 1 1 1 ) 0 1 ) 1 )
자이제 문제에 대한 이해가 끝났다.
이제 N x N 의 행렬이 들어오면 ( N은 1~64 )
( 0 0 0 0 ) 식의 형태로 출력해줘야 하는 프로그램을 짜야한다
내가 시도한 로직은 이렇다.
* 첫번째 입력값을 int N에 저장한다.
* N행만큼 buffer에 저장
* 수 N을 매개변수로 전달받는 메서드 check를 생성
check ( int N ) 의 기능은 아래와 같다.
String str 1 ,2 ,3 ,4 생성
int count = 1;
1) 행렬의 값을 (N/4)^2 번만큼 이중 반복문을 실행
2) 첫번째의 값을 지역변수 int T에 저장
3) 반복문이 종료될때까지 행렬의 값과 T의값을 비교
4) T의값과 다르다면
if( count == 1){
str1 = "(" + check( int N/2 ) +")"
}
~~else if(count == 4 ){
str2 = "(" + check( int N/2) +")"
}
이후 break;
5) 내부 반복문 탈출할때마다 count++;
6) 반복문 이끝나면
return str1 + str2 + str3 + str4;
* check() 4회실행
[ 결과 ]
문제의 접근 방식은 옳았다고 판단되지만
행렬의 값이 2번이상 나눠지면 제대로된 값을 호출하지 못하였다.
[ 원인 & 해결책 ]
1- 원인 ) 1차원 배열을 N개만큼 만들어서 행렬처럼 사용한 점이다.
행렬의 값이 4분의1로 분할되어 호출될때마다
입력된 N을 2로나누면서 재 탐색을 해야하는
분할된 행렬을 구할수는 있었다.
하지만
모든 분할된 행렬을 2사 분면에 새롭게 생성하고
2사분면만 계속해서 재검색을 한후 return값을 받음과동시에
N개의 행렬값은 모두 처음으로 초기화 시켜주는 부분이 문제를 발생시켰다.
그것은
탐색할 행렬은 4분의1로 나눴지만
1,3,4분면을 검색하는 반복문이 전부다 2사분면의 위치를 검색했던 것이다.
글을 정리하면서도 느끼지만
분할될때의 자세한 로직을 미리 생각하지 못했던점이
점점더 문제풀이를 곤란하게 만들
1. - 해결책)
* 행렬을 재구성 하지 않고 주어진 행렬을
읽게하는 위치만 변경되되록
새로운 변수를 설정해주자
-> 주어진 배열을 탐색하는건데 재귀가 호출될때마다
새롭게 배열값을 재생성하고 반복문의 시작위치를 계속해서 바꿔주는 걸 동시에 하는 것자체가
더 복잡하고 비효울적인 방법이였다
* 2차,3차원 배열을 적극 활용하자!
-> [][] 2차원 배열을 사용할 생각을 정말 전~혀 못했다..
[ 정답을 보고 수정한 코드 ]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import javax.swing.text.AbstractDocument.BranchElement;
public class L_1992
{
static int[][] inputArray;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
inputArray = new int[N][N];
for(int i=0; i<N; i++)
{
String str = br.readLine();
for(int j=0; j<N; j++)
{
inputArray[i][j] = str.charAt(j)-'0'; // '0'은 ASCILL 48
}
}
quadRun(0,0,N);
System.out.println(sb);
}
static void quadRun(int x, int y, int size)
{
if(valueCheck(x,y,size))
{
sb.append( inputArray[x][y] );
return;
}
int newSize = size/2;
sb.append("(");
quadRun(x, y, newSize);
quadRun(x, y+newSize, newSize);
quadRun(x+newSize, y, newSize);
quadRun(x+newSize, y+newSize, newSize);
sb.append(")");
}
// 주어진 배열의 값이 하나로 일치하는지 안하는지 체크
static boolean valueCheck(int x, int y, int N)
{
int checkValue = inputArray[x][y];
for(int i=x; i<x+N; i++)
{
for(int j=y; j < y+N; j++)
{
if(checkValue != inputArray[i][j]) return false;
}
}
return true;
}
}