[백준] 2447 별 찍기 - 분할정복 + 재귀 JAVA

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

2447번: 별 찍기 - 10

코드설명

재귀를 활용한 분할정복 문제입니다.

 

문제로직입니다.

1. 문제에서 핵심은, 5번째 별을 찍을때 해당 공간은 빈공간으로 처리해야합니다.

여기서 5번째 별이란, (0,0) -> (0, 1) -. (0,2) -> (1, 0) -> (1, 1) 일떄 (1,1) 을 의미합니다.

2. 빈공간이 찍히는 flag인 emptySpace를 매개변수로 함꼐 보내어 빈공간찍을때와 아닐떄를 구분합니다.

3. size가 1 이라면 더이상 분리할 수 없으므로 ' * ' 을 찍습니다.

 

 

코드

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

public class Main {
	public static int N, R, C;
	public static char[][] map;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new char[N][N];
    	
    	divideConquer(0, 0, N, false);
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			sb.append(map[i][j]);
    		}
    		sb.append("\n");
    	}
    	System.out.println(sb.toString());
    	
    }
	
	public static void divideConquer(int r, int c, int size, boolean emptySpace) {
		if(emptySpace == true) { //빈 공간일경우 해당 Size만큼 빈공간으로 채웁니다.
			for(int i=r; i<r + size; i++) {
				for(int j=c; j<c + size; j++) {
					map[i][j] = ' ';
				}
			}
			return ;
		}
		if(size == 1) { //한개 크기면 * 체크합니다.
			map[r][c] = '*';
			return ;
		}
		
		int nSize = size/3;
		int count = 0;
		for(int i=r; i<r + size; i+= nSize) { //각 size만큼 돌며 분핳정복을 합니다. 이떄 증가분은 nSize입니다.
			for(int j=c; j<c + size; j+= nSize) {
				count+=1;
				if(count == 5) { //5번째 공간은 빈공간입니다.
					divideConquer(i, j, nSize, true);
				}else {
					divideConquer(i, j, nSize, false);
				}
				
			}
		}
		
	}
	
}