[백준,BOJ 2447] 별 찍기 - 10(JAVA 구현, 재풀이)

-내 생각

  이번에 한 번 풀어봤던 문제여서 조금만 고민하면 풀 수 있을 줄 알았는데, 풀이 방법의 감이 잡히질 않았다. n을 3으로 가정하고 작성하면 잘 출력이 되는데 n이 9일 때 안되거나, 반대로 n이 9일 때를 가정하고 작성하면 n이 3일 때가 잘 출력되지 않았다... ㅋㅋㅋ

 

  그래도 처음 풀 때는 거의 다른 분들의 블로그에서 풀이를 보고 베끼다시피 했는데, 이번엔 참고 정도만 하면서 풀 수 있어서 좋았다.

 

-해법

  다른 분의 블로그에서 얻은 힌트는 하나의 분할에서 4번 째는 고려하지 않는다는 점이었다. 아래의 블로그를 참고하기를 바란다. 다른 문제들도 이해하기 쉽게 올려주셔서 보기 편하다.

[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]

  이후에는 n의 경우에 따라 시작하는 점을 옮겨주는 것이 중요하다. 이는 코드를 보면 이해하기 쉬울 것이다.

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static char arr[][]; // 별을 찍을 배열
    
	static void star(int n,int x,int y) { // 별 찍기 재귀호출 함수
		int count =0; // 4번 째는 고려하지 않기 위해 사용하는 변수
		if(n==1) { // 재귀함수 종료조건, n/3이 1이 되었을 땐 별을 찍어주고 함수를 종료
			arr[x][y] = '*';
			return;
		}
		
		for(int i=x;i<n+x;i+=n/3) { // 전달받은 x좌표 시작; 분할된 n + x좌표 까지; n/3 씩 증가
			for(int j=y;j<n+y;j+=n/3) { // 위와 동일
				
				if(count == 4) { // 4번째면 0으로 초기화 후 넘긴다.
					count =0;
				}else { 
					star(n/3,i,j); // 분할하여 재귀호출, 좌표값을 인자로 넘긴다.
					count++; // 몇 번찍었는지 체크
				}
			}
		}
	}
	
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt(); // 3의 배수 n 입력
        
        arr = new char[n][n]; // n x n 크기의 배열 객체 생성
        
        for(int i=0;i<n;i++) { // 조건에 따라 별을 찍어줄 것이기 때문에 초기에 전부 공백으로 초기화
        	Arrays.fill(arr[i], ' ');
        }
        
        star(n,0,0); // n의 크기, x좌표, y좌표를 전달
        
        for(int i=0;i<n;i++) { // 별 찍기 판 출력
        	System.out.println(arr[i]);
        }
        
        in.close();
    }
}

  다시 보니 내가 나중에 코드를 보더라도 이해 못할 것 같아서 다시 자세히 설명을 작성해놓아야겠다. 

 

  1. 별을 찍을 배열 객체를 생성한다.

  2. 모두 공백으로 채운다.

  3. n의 크기와 x좌표 0, y좌표 0으로 재귀함수 스타트

  4. n에 상관없이 해당 분할에는 3번 진행 후, 공백 처리함을 인지 후 count 변수 선언

  5. 재귀함수이므로 종료 조건 생성, n이 1일 때 해당 좌표에 별을 찍고 종료

  6. 좌표 탐색을 위한 2중 for문 작성

  6-1. x,yx, y 좌표의 시작은 전달받은 x, y 좌표로 시작한다. 초기에는 0,0이며 종료 조건은 분할된 n의 크기 + x, y좌표, 증가는 분할 크기만큼 증가

  이는 n이 9라고 가정했을 때 아래의 표와 같다.

n	시작(x,y)	종료(x,y)	증감
9	0,0	9,9 0부터 9까지 3씩 증가하며 탐색	9/3 = 3 n이 9일 때는 0,0 / 0,3 / 0,6...이므로 별을 찍기 시작하는 지점이 3씩 증가한다.
3 n이 3일 때 별을 찍기 위해 분할된 n을 재귀호출	0,0 위에서 전달받은 x,y 좌표	3,3 분할된 n이 3이므로 3+x,y 좌표	3/3 = 1 n이 3일 때는 0,0 / 0,1/ 0,2... 이므로 별을 찍기 시작하는 지점이 1씩 증가한다.
1 3을 마지막으로 분할 해 1	0부터 2까지 1씩 증가하며 x,y 좌표가 전달되어 별이 찍힌다.	n이 1이므로 별을 찍음	n이 1이므로 별을 찍음
9 n이 9일 때 첫 번째 분할이 끝나 별을 모두 찍었기 때문에 다시 9로 돌아온다.	0,3 위의 증감에 따라 y좌표만 우선 3이 증가.	9,9 종료조건은 그대로이다.	9/3 = 3  증감역시 그대로
3 0,3으로 시작하는 좌표에 별을 찍기 위해 다시 분할	0,3 위에서 전달받은 x,y 좌표	3,6 y좌표가 변했으므로 분할 n인 3+y좌표로 종료조건 증가	3/3 = 1 위와 마찬가지로 n이 3일 때는 1씩 증가한다.
1 다시 3을 분할 해 1	x좌표는 0부터 2까지 1씩 증가 y좌표는 3부터 5까지 1씩 증가하면서 전달되어 별이 찍힌다.	별 찍기	별 찍기
9 두 번째 분할 후 별을 찍었으므로 다시 돌아온다.	0,6	9,9	3 이후 동일

  6-2. 이 과정에서 별을 찍은 개수를 count로 증가시켜 판단, 4일 때는 넘어가고 다시 초기화 시켜준다.

끝!