백준 2447번: 별 찍기 - 10 [분할정복][재귀] - Java

www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

***
* *
***

패턴 규칙을 따르며, 센터는 항상 ' ' 공백으로 되어있는 규칙을 확인할 수 있다.

큰 거에서 작은 거부터.. 확인한다.

(9라면 전체 9*9 본거부터 3*3 조각 나눠서 보고 1*1 조각 나눠서 보고..)

 

<풀이 방법>

1. 더이상 나눌 수 없는가? (N==1)

없다면 출력 ( 센터면 공백, 아니면 * 출력)

2. 나눌 수 있다면 3으로 나눠서 9등분 시킨다.

이 때, 중요포인트는 지금 얘기 센터에 해당하는 위치인지 아닌지를 판별해주는 것이다.

3의 거듭제곱일 경우에 항상 i=1,j=1일때 해당 사각형의 센터의 첫 좌표값 가게 된다. true처리 해주기.

이미 true인 경우에는 pass한다. 왜? 센터인 사각형에서는 무조건 공백출력이기 때문에!

그 후, 다시 solve 재귀함수를 통하여 조각된 9등분을 1개씩 다시 반복한다.

 

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main  {

	public static Character[][] map;
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		map = new Character[N][N];
		//solve
		solve(0,0,N,false);

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				bw.append(map[i][j]);
			}
			bw.append("\n");
		}
		
		bw.flush();
	}

	public static void solve(int row, int col, int N,boolean isCenter) {

//		System.out.println("행렬 : "+row+","+col+","+isCenter+", n = "+N);
		
		//더이상 나눌 수 없는가 ?
		if(N==1) {
			//센터인가?
			if(isCenter)
				map[row][col]=' ';
			else
				map[row][col]='*';
		}
		else {
			//아니라면 전체를 3으로 나눠서 9등분한다.
			int cut = N/3;
			for (int i = 0; i < 3; i++) {
				for (int j = 0; j < 3; j++) {
					// 해당 x좌표가 이 정사각형의 센터 부분인가?
					// 이미 센터 부분인 경우에는 굳이 확인하지 않음..
					boolean flag = isCenter;
					if(!isCenter)
						flag = (i==1 && j==1 ? true : false);
					
					
					solve(row+(i*cut),col+(j*cut),cut,flag);
				}
			}
			
		}

	}
}

 

 

Array 자체에 모두 ' '공백을 처음에 초기로 세팅해놓고

isCenter를 if문에 걸어서 애초에 센터가 아닌 애들만 * 을 찍어주는 로직도 있다.

아예 isCenter없익 그냥 i=1, j=1이면 continue;를 해도 된다.

 

 

설명이 더 어렵군....

 

fbtmdwhd33.tistory.com/21