ํ๋ฐฑ ์์์ ์์ถํ์ฌ ํํํ๋ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ก ์ฟผ๋ ํธ๋ฆฌ(Quad Tree)๋ผ๋ ๋ฐฉ๋ฒ์ด ์๋ค. ํฐ ์ ์ ๋ํ๋ด๋ 0๊ณผ ๊ฒ์ ์ ์ ๋ํ๋ด๋ 1๋ก๋ง ์ด๋ฃจ์ด์ง ์์(2์ฐจ์ ๋ฐฐ์ด)์์ ๊ฐ์ ์ซ์์ ์ ๋ค์ด ํ ๊ณณ์ ๋ง์ด ๋ชฐ๋ ค์์ผ๋ฉด, ์ฟผ๋ ํธ๋ฆฌ์์๋ ์ด๋ฅผ ์์ถํ์ฌ ๊ฐ๋จํ ํํํ ์ ์๋ค.
์ฃผ์ด์ง ์์์ด ๋ชจ๋ 0์ผ๋ก๋ง ๋์ด ์์ผ๋ฉด ์์ถ ๊ฒฐ๊ณผ๋ "0"์ด ๋๊ณ , ๋ชจ๋ 1๋ก๋ง ๋์ด ์์ผ๋ฉด ์์ถ ๊ฒฐ๊ณผ๋ "1"์ด ๋๋ค. ๋ง์ฝ 0๊ณผ 1์ด ์์ฌ ์์ผ๋ฉด ์ ์ฒด๋ฅผ ํ ๋ฒ์ ๋ํ๋ด์ง๋ฅผ ๋ชปํ๊ณ , ์ผ์ชฝ ์, ์ค๋ฅธ์ชฝ ์, ์ผ์ชฝ ์๋, ์ค๋ฅธ์ชฝ ์๋, ์ด๋ ๊ฒ 4๊ฐ์ ์์์ผ๋ก ๋๋์ด ์์ถํ๊ฒ ๋๋ฉฐ, ์ด 4๊ฐ์ ์์ญ์ ์์ถํ ๊ฒฐ๊ณผ๋ฅผ ์ฐจ๋ก๋๋ก ๊ดํธ ์์ ๋ฌถ์ด์ ํํํ๋ค
N รN ํฌ๊ธฐ์ ์์์ด ์ฃผ์ด์ง ๋, ์ด ์์์ ์์ถํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ์ซ์ N ์ด ์ฃผ์ด์ง๋ค. N ์ ์ธ์ ๋ 2์ ์ ๊ณฑ์๋ก ์ฃผ์ด์ง๋ฉฐ, 1 โค N โค 64์ ๋ฒ์๋ฅผ ๊ฐ์ง๋ค. ๋ ๋ฒ์งธ ์ค๋ถํฐ๋ ๊ธธ์ด N์ ๋ฌธ์์ด์ด N๊ฐ ๋ค์ด์จ๋ค. ๊ฐ ๋ฌธ์์ด์ 0 ๋๋ 1์ ์ซ์๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ์์์ ๊ฐ ์ ๋ค์ ๋ํ๋ธ๋ค.
์ถ๋ ฅ
์์์ ์์ถํ ๊ฒฐ๊ณผ๋ฅผ ์ถ๋ ฅํ๋ค.
๋ชจ๋ ๋ถ๋ถ์ ์ซ์๊ฐ ์ผ์นํ์ง ์์ผ๋ฉด 4๊ฐ ๋ถ๋ถ์ผ๋ก ๋๋์ด์ ์์ถํด์ผํจ
์์ถํ ๊ฒฐ๊ณผ๋ ์์ ์๋ ์ซ์์ ๋์ผ
4๊ฐ ๋ถ๋ถ์ผ๋ก ๋๋ ์ ํฉ์น๊ธฐ (๋ถํ ์ ๋ณต)
1 : (0,0) 2: (half, 0) 3: (0, half) 4: (half, half)
1) 4๊ฐ ๋ถ๋ถ์ผ๋ก ๋๋ ์ ํฉ์น๊ธฐ(๋ถํ ์ ๋ณต)
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++)
quad(x+half*j, y+half*i, half);
}
import java.io.*;
public class Divide_1 {
static int arr[][], m;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n][n];
for(int i=0; i<n; i++) {
String s[] = br.readLine().split("");
for(int j=0; j<n; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
quad(0,0,n);
}
static void quad(int x, int y, int half) {
if(check(x,y,half))
System.out.print(m);
else {
System.out.print("(");
half /= 2;
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++)
quad(x+half*j, y+half*i, half);
}
System.out.print(")");
}
}
static boolean check(int x, int y, int half) {
for(int i=y; i<y+half; i++) {
for(int j=x; j<x+half; j++) {
if(arr[y][x] != arr[i][j] )
return false;
}
}
m = arr[y][x];
return true;
}
}
์ฑ๊ณต~