[백준 2448번/JAVA] 별 찍기 - 11 (문제 풀이, 코드)

별 찍기 -11

 

예제는 아래와 같다.

[문제]

N = 3 * 2^k 이다. N번째 줄까지 위와 같은 규칙으로 별을 찍어야한다.

 

[풀이]

별 찍기 문제는 항상 규칙을 찾는 문제다. 어떤 규칙을 찾느냐에 따라 코드가 달라질 것 같다.

나는 아래와 같은 규칙을 찾았다.

• 내가 정한 삼각형은 3줄이다.
• 가장 윗 줄의 가운데에 별 하나(위 꼭짓점)
• 두 번째 줄 가운데 칸을 비우고 양 옆으로 별 하나
• 마지막 줄은 별 5개. 내가 만들 삼각형의 기준은 아래 그림과 같다.

• 그리고 삼각형의 아래 왼쪽 꼭짓점, 아래 오른쪽 꼭짓점 밑 줄의 옆 칸으로부터 새로운 삼각형이 시작된다.
• 단, 아래와 같은 경우는 삼각형의 꼭지점이더라도 만들어질 수 없다.
• 삼각형 밑변의 꼭짓점에서부터 ±2칸 사이에 다른 삼각형의 꼭짓점이 발견되면 해당 꼭짓점으로부터 삼각형이 생성되는 것은 불가능하다!

 

[내 코드 알고리즘]

1. 별과 ' '(빈칸)을 넣을 2차원 배열을 만들었다.
   • 모든 칸은 빈칸으로 초기화한다.
   • 2차원 배열의 행은 N, 열은 2*N-1
   • 열의 경우 k에 1,2,3을 대입하여 규칙을 찾아냈다.
   • 이하 star[N][2*N-1]로 부르도록 하겠다.
2. 첫 삼각형은 탐색할 꼭짓점이 없으므로 직접 만든다.
   • make(0,N-1) 메서드를 사용했다. 해당 메서드는 아래와 같이 동작한다.
   • star[0][N-1] = '*'; 0번째 줄의 N-1칸 자리에 삼각형의 가장 위쪽 꼭짓점을 찍는다.
   • star[1][N-2] = '*'; star[1][N] = '*'; 1번째 줄의 N-2, N자리에 별을 찍는다.
   • star[2][N-3]~[N+2] = '*'; 5개 별 찍는다.
   • 위에 정의했던 삼각형을 찍는 메서드다.
3. 삼각형의 아래 꼭짓점이 어딘지 탐색한다.
   
   • find(3,N-3) 메서드를 사용했다. 해당 메서드는 아래와 같이 동작한다.
   • 3번째 줄의 윗 줄인 2번째 줄에서 N-3번째 칸이 *인지 확인한다.
   • *이라면 왼쪽 칸이 ' '인지 확인한다.
   • 왼쪽 칸이 ' '라면 해당 삼각형의 왼쪽 꼭짓점을 찾았다! 
   • 해당 위치보다 2칸 왼쪽에 *이 있는지 확인한다(이 경우는 삼각형을 만들 수 없다.)
   • 없다면 make(3,N-4) // 3번째줄의 N-4칸에 '*'을 찍어야하니까!
   • 만약 왼쪽 꼭짓점이 아니었다면 오른쪽 꼭짓점도 비슷하게 확인한다!
   • 해당 칸이 꼭짓점이 아닌 칸이라면 +1을 해서 다음 칸을 확인한다.
     • find(3,N-3)을 할 때, 왼쪽 꼭짓점을 알려주는 방식으로 하려고 parameter를 두 개 받았으나, 이 경우 한 쪽으로만 치우친 삼각형이 만들어져서 첫 삼각형 다음부터는 find(a,0)을 사용한다.
   • 해당 줄의 꼭짓점 탐색이 모두 끝났다면 find(6,0)
   • 만약 6==N이면 종료한다.
4. StringBuilder에 star 2차원 배열의 값을 다 담아서 출력한다.

 

[코드]

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

public class stareleven_2448 {
	static int N;
	static char[][] star;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		star = new char[N][N*2-1];
		for(int i=0; i<N; i++)
			for(int j=0; j<N*2-1; j++)
				star[i][j] = ' ';
		
		/* 첫 삼각형만 예외로 미리 만들어서 star 에 넣어둠.*/
		make(0,N-1);
		find(3,N-3);
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			for(int j=0; j<N*2-1; j++)
				sb.append(star[i][j]);
			sb.append("\n");
		}
		System.out.println(sb);
	}
	public static void find(int a, int b) {
		if(a>=N) return;
		for(int i=0; i<N*2-1; i++) {
			if(b+i>=N*2-1) break;
			/* 왼쪽 꼭짓점인 경우*/
			if(star[a-1][b+i] == '*' && star[a-1][b+i-1] == ' ') {
				if(star[a-1][b+i-2] != '*')
					make(a,b+i-1);
			}
			/* 오른쪽 꼭짓점인 경우 */
			else if(star[a-1][b+i] == '*' && star[a-1][b+i+1] == ' ') {
				if(star[a-1][b+i+2] != '*')
					make(a,b+i+1);
			}
		}
		find(a+3,0); // 삼각형의 왼쪽 꼭짓점이 어딘지 알려주기!
	}
	public static void make(int a, int b) {
		// a : 삼각형의 행 시작 위치
		// b : 삼각형의 열 시작 위치
		star[a][b] = '*';
		star[a+1][b-1] = '*';
		star[a+1][b+1] = '*';
		for(int i=0; i<5; i++)
			star[a+2][b-2+i] = '*';
		
	}
}

 

GitHub에 티스토리에 올리지 않은 코드들도 업로드 되어 있습니다.

https://github.com/MOBUMIN/BJalgorithm/blob/master/stareleven_2448.java

MOBUMIN/BJalgorithm