📚 오늘의 문제.

📝 문제 1. 별 찍기 - 10

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

1. 문제 설명

   

2. 문제 풀이

   재귀 출력이 간단하나 출력하는 과정에서 어려움을 겪게되는 문제이다.

   간단하게 nxn의 2차원 배열을 만들고 문제 Z 처럼 영역을 나눠서 진행하면 되지 않을까?

   문제 최대 입력값인 3^8 = 6,561 이므로

   3^16 = 6561 * 6561 = 43,046,721 크기의 배열이 만들어지니깐 공간복잡도는 static으로 만들면 괜찮을 것 같았다.

   하지만 해당 부분을 구현하는것이 여간 어려운 것이 아니었다.

   일단 모든 행렬을 *로 초기화 시키고 공백 부분을 비우는 과정으로 구현했다.

   해당 풀이의 수도코드

   board[n][n] // board 배열 '*' 으로 초기화
   
   재귀함수(n, r, c):
       # 기본 사례(Base Case).
       만약 n이 3이라면:
           3x3 행렬의 가운데를 비운다.
           board[r + 1][c + 1] = ' '
           return
   
       # 행렬 크기 1/3을 계산한다.
       oneThird = n / 3
   
       # n x n 배열의 가운데 부분을 비운다.
       for i = r + oneThird to r + 2 * oneThird - 1:
           for j = c + oneThird to c + 2 * oneThird - 1:
               board[i][j] = ' '
   
       # 작아진 부분에서도 재귀적으로 진행하며
       # 0 1 2
       # 3 4 5
       # 6 7 8 순으로 재귀 호출
       
       재귀함수(oneThird, r, c)                               # 0
       재귀함수(oneThird, r, c + oneThird)                    # 1
       재귀함수(oneThird, r, c + 2 * oneThird)                # 2
       재귀함수(oneThird, r + oneThird, c)                    # 3
       재귀함수(oneThird, r + oneThird, c + oneThird)         # 4
       재귀함수(oneThird, r + oneThird, c + 2 * oneThird)     # 5
       재귀함수(oneThird, r + 2 * oneThird, c)                # 6
       재귀함수(oneThird, r + 2 * oneThird, c + oneThird)     # 7
       재귀함수(oneThird, r + 2 * oneThird, c + 2 * oneThird) # 8

   package 재귀;
   
   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   
   public class boj_2447 {
   
     static char[][] board;
   
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringBuilder sb = new StringBuilder();
       int n = Integer.parseInt(br.readLine()); // n = 3^k 형태. 3, 9, 27
       board = new char[n][n];
   
       //board 초기화
       for (int i = 0; i < board.length; i++) {
         for (int j = 0; j < board.length; j++) {
           board[i][j] = '*';
         }
       }
   
       recursion(n, 0, 0);
   
       for (int i = 0; i < board.length; i++) {
         for (int j = 0; j < board.length; j++) {
           sb.append(board[i][j]);
         }
         sb.append("\n");
       }
   
       System.out.println(sb.toString());
     }
   
     private static void recursion(int n, int r, int c) {
       if (n == 3) {
         board[r + 1][c + 1] = ' '; // 가운데를 비운다.
         // log
   //      System.out.println("--------------" + n / 3 + "--------------");
   //      for (int i = 0; i < board.length; i++) {
   //        for (int j = 0; j < board.length; j++) {
   //          System.out.print(board[i][j]);
   //        }
   //        System.out.println();
   //      }
   
         return;
       }
   
       int oneThird = n / 3;
   
       for (int i = r + oneThird; i < r + 2 * oneThird; i++) {
         for (int j = c + oneThird; j < c + 2 * oneThird; j++) {
           board[i][j] = ' ';
         }
       }
       // 0 ~ m-1 부분 비우기
       recursion(oneThird, r, c);
       recursion(oneThird, r, c + oneThird);
       recursion(oneThird, r, c + oneThird * 2);
   
   		
       recursion(oneThird, r + oneThird, c);
       //recursion(oneThird, r + oneThird, c * oneThird); // 사실 가운데는 비워지기에 해당 부분은 의미 없다.
       recursion(oneThird, r + oneThird, c + 2 * oneThird);
   
       recursion(oneThird, r + oneThird * 2, c);
       recursion(oneThird, r + oneThird * 2, c + oneThird);
       recursion(oneThird, r + oneThird * 2, c + 2 * oneThird);
     }
   
   }
   

이렇게 구현했는데 흠… 문제를 아홉부분으로 나눠 재귀적으로 코드를 나눠 엄청 보기 힘들다.

간단히 설명하자면 각 영역을 9개(가운데는 비워주면 되므로 결국 8개다)의 영역으로 나누어 N == 3 이 될때까지 가운데를 비워가면서 재귀를 돌린다.

다른 풀이 1.

스터디원이 빈칸을 별로 초기화하는 방법으로 TIL과 풀이코드를 적어 해당 부분을 첨부하겠다.

https://velog.io/@growing_jd/백준-자바-2447

해당 코드는 boolean 인수를 받아서 5번째(가운데 부분)을 따로 트래킹하는 풀이이다.

https://github.com/lee-JunR/STD_algorithm/pull/41/files#diff-610779056bcf989764ea00b5131b9c648630623373a3317f542e695e7620bac9

다른 풀이 2.

문자열을 활용해 각 단계를 정말 쌓듯이 구현할 수 있다

이렇게 하면 depth가 N/3이면 된다.

주석을 달아놨으니 한번 확인해보도록..

package 재귀;

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    // 1. 프로그램 시작
    // 2. Scanner 객체를 생성하여 사용자 입력을 받음.
    Scanner scanner = new Scanner(System.in);
    
    // 3. 사용자가 입력한 값을 N 변수에 저장.
    int N = scanner.nextInt();
    
    // 4. Scanner 객체를 닫음.
    scanner.close();

    // 5. 별 그리기 함수 호출
    // 6. drawStars(N) 함수를 호출하여 결과를 stars 배열에 저장.
    String[] stars = drawStars(N);
    
    // 7. 결과 출력
    // 8. stars 배열의 각 줄을 출력.
    for (String line : stars) {
      System.out.println(line);
    }
  }

  // 9. 별 그리기 함수 정의
  //    입력: n (배열의 크기)
  //    출력: n x n 배열을 나타내는 문자열 배열
  public static String[] drawStars(int n) {
    // 10. 기본 사례 (Base Case)
    //    만약 n이 1이면, 배열에 별 하나를 넣고 반환.
    if (n == 1) {
      return new String[]{"*"};
    }

    // 11. 재귀 호출
    //    n을 3으로 나눈 값을 입력으로 drawStars 함수를 재귀적으로 호출.
    //    재귀 호출 결과를 Stars 배열에 저장.
    String[] Stars = drawStars(n / 3);
    
    // 12. 새로운 배열 생성
    //    크기가 n인 새로운 배열 L을 생성.
    String[] L = new String[n];

    int index = 0;

    // 13. 배열 채우기
    //    Stars 배열의 각 줄을 세 번 반복하여 새로운 배열의 첫 번째 세 부분을 채움.
    for (String star : Stars) {
      L[index] = star + star + star;
      index++;
    }
    //    Stars 배열의 각 줄을 공백과 함께 새로운 배열의 두 번째 세 부분을 채움.
    for (String star : Stars) {
      L[index] = star + " ".repeat(n / 3) + star;
      index++;
    }
    //    Stars 배열의 각 줄을 세 번 반복하여 새로운 배열의 세 번째 세 부분을 채움.
    for (String star : Stars) {
      L[index] = star + star + star;
      index++;
    }

    // ----- log -----
    // System.out.println("Current stage n = " + n);
    // for (String line : L) {
    //   System.out.println(line);
    // }
    // System.out.println();
    // ---------------

    // 14. 새로운 배열 반환
    //    채운 배열 L을 반환.
    return L;
  }
}