[백준] 2447. 별 찍기 10

문제 링크

[백준] 2447. 별 찍기 10

풀이 과정

먼저 규칙을 찾습니다. N은 3의 거듭제곱이므로, 3, 9, 27, … 등으로 주어집니다. 문제 예제에서는 27x27 크기의 패턴이 주어졌으므로, 3x3 다음 크기인 N이 9일때의 모습을 그려봅니다.

9x9 크기의 패턴을 그려보며 다음과 같은 특징을 찾을 수 있습니다.

• 정 가운데의 좌표는 (4, 4) 이다.
• 정 가운데를 기준으로 8방향(↖︎, ↑, ↗, ←, →, ↙, ↓, ↘︎)에 3x3 크기의 패턴이 존재한다.
• 9x9 크기의 패턴의 정 가운데에서부터 8방향 각각의 3x3 크기의 패턴의 정 가운데 좌표까지의 거리는 델타 배열 요소에 3을 곱해 이동시킨 것과 같다.

27x27 크기의 패턴도 위와 같은 특징을 갖는지 확인합니다.

• 정 가운데의 좌표는 (13, 13) 이다.
• 정 가운데를 기준으로 8방향에 9x9 크기의 패턴이 존재한다.
• 27x27 크기의 패턴의 정 가운데에서부터 8방향 각각의 9x9 크기의 패턴의 정 가운데 좌표까지의 거리는 델타 배열 요소에 9를 곱해 이동시킨 것과 같다.

따라서, 다음과 같은 규칙을 일반화 할 수 있습니다.

• NxN 크기의 패턴의 정 가운데 좌표는 (N/2, N/2) 이다.
• NxN 크기의 정 가운데를 기준으로, 8방향에 (N/3, N/3) 크기의 패턴이 존재한다.
• NxN 크기의 패턴의 정 가운데에서부터 8방향 각각의 N/3xN/3 크기의 패턴의 정 가운데 좌표까지의 거리는 델타 배열 요소에 N/3 을 곱해 이동시킨 것과 같다.

static void solve(int n, int x, int y) {
    if (n == 3) {
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            map[nx][ny] = '*';
        }

        return;
    }

    for (int d = 0; d < 8; d++) {
        int nx = x + dx[d] * n / 3, ny = y + dy[d] * n / 3;
        solve(n / 3, nx, ny);
    }
}

따라서, 다음과 같이 N을 분할해 배열을 그릴 수 있습니다.

1. N이 3보다 큰 3의 거듭제곱일 때는, N/3의 크기와 8방향 각각의 정 가운데 좌표의 위치 정보를 넘겨 작은 단위로 분할한다.
2. N이 3일때는 가장 기본 단위이므로, 갖고 있는 좌표를 기준으로 별을 그린다.

코드

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

public class Main {
    static char[][] map;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}, dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        map = new char[N][N];

        for (int i = 0; i < N; i++) Arrays.fill(map[i], ' ');

        solve(N, N / 2, N / 2);

        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);
    }

    static void solve(int n, int x, int y) {
        if (n == 3) {
            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                map[nx][ny] = '*';
            }

            return;
        }

        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d] * n / 3, ny = y + dy[d] * n / 3;
            solve(n / 3, nx, ny);
        }
    }
}