BOJ 10994 | 별찍기 - 19 | 해결 과정 정리 | 재귀 vs 재귀X

백준 10994 별찍기 문제를 해결해보았다. 

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

10994번: 별 찍기 - 19

 

 

---

◆ 문제 해결 과정 : (재귀 X)

 

 

 

---

◆ 소스코드 (재귀X)

위 방법으로 구현한 결과

위 문제해결 과정을 바탕으로 다음처럼 작성해나갔다.

 

- draw_step_of(k) : k단계 박스를 그리는 메서드

- print_else_line(k) : k단계 박스를 그리는 메서드 안에 사용함.

                           박스 윗라인이 있는 부분 말고 다른 라인을 그린다.

                           (=> box side만을 그리는 부분)

- flag를 설정하여서 box의 윗부분, 아랫부분을 그리는 방법을 달리하였다.

  단순히, 위에 소개한 두 메서드의 순서를 서로 뒤바꿔주었을 뿐이다.

 

'박스그리기의 단계'를 문제해결의 기준으로 삼은 만큼,

메서드의 매개변수는 모두 박스의 단계 k로 통일했다.

 

import java.util.*;

public class Main{

  public static boolean flag = false;
  public static int max_stars, N;

  public static void print_else_line(int k){
    // box k개 -> 양옆에 k개의 별 찍기 (k != 3)
    // 그럼 공백은 -> max_stars - k*2*2
    if (k != N) {
      System.out.print("* ".repeat(k)
                      + " ".repeat(max_stars - k*2*2)
                      + " *".repeat(k) + "\n"); 
    }
  }
  
  public static void draw_step_of(int k, boolean flag){
    if (flag)
      print_else_line(k);
    
    // box k개 단계
    // - count of "*" or " " except line : ((k-1)*2)*2
    // - count of stars at line : max_stars - ((k-1)*2)*2
    System.out.print("* ".repeat((k-1))
                    + "*".repeat((max_stars - ((k-1)*2)*2))
                    + " *".repeat((k-1)) + "\n");
    
    if (!flag)
      print_else_line(k);
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    max_stars = (2*N-1)*2 - 1;
    sc.nextLine();

    for(int i = 1; i <= N; i++)
      draw_step_of(i, flag);

    flag = true;
    for (int i = N-1; i >= 1; i--)
      draw_step_of(i, flag);
      
    sc.close();
  }
}

 

---

◆ 재귀 구현

이게 훨씬 낫다.

재귀로 푼 결과

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

public class Main{
  // 1 <= input <= 100
  // max_length : (2*100-1)*2-1 => 397
  public static char[][] matrix = new char[397][397];
  public static int maxLength = 0;

  public static void recurBox(int x, int y, int step){
    if (step == 1){
      matrix[y][x] = '*';
      return;
    }
    /*
    input : 3
    step3 : line length : 9
    step2 : line length : 5
    step1 : line length : 1
    generalization : step k, line length is (2*k-1)*2-1 
    */
    int length = (2 * step - 1) * 2 - 1;
    
    for (int i = 0; i < length; i++){
      // upper, bottom line
      matrix[y][x+i] = '*';
      matrix[y+length-1][x+i] = '*';
    }
    for (int i = 0; i < length-1; i++){
      // both side line
      matrix[y+i][x] = '*';
      matrix[y+i][x+length-1] = '*';
    }
    
    recurBox(x+2, y+2, step - 1);
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    int n = Integer.parseInt(br.readLine());
    maxLength = (2 * n - 1) * 2 - 1;

    for(int i = 0; i < maxLength ; i++){
      for(int j = 0; j < maxLength; j++)
        matrix[i][j] = ' ';
    }
    
    recurBox(0, 0, n);

    for(int i = 0; i < maxLength; i++){
      for(int j = 0; j < maxLength; j++)
        bw.write(matrix[i][j]);
      bw.newLine();
    }
    
    br.close();
    bw.flush();
    bw.close();
  }
}