Post

[BaekJoon] 2447번 - 별 찍기 - 10 [Java][C++]

Posted
By FickleBoBo
3 min read
[BaekJoon] 2447번 - 별 찍기 - 10 [Java][C++]

문제 링크

1. 아이디어


프랙탈 형태로 별을 출력하는 문제로 반복되는 구조를 보면 현재 바라보는 영역을 가로, 세로 각각 3등분해서 9개의 작은 정사각형을 만들었을 때 정가운데 정사각형은 비우고 나머지에 대해 같은 행위를 반복하는 것을 볼 수 있다. 방문 체크 배열과 재귀를 활용해서 이를 재귀적으로 탐색하며 크기 1의 정사각형이 될 때까지 반복하면 된다.

2. 코드


1. 풀이 [Java]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.io.*;

public class Main {

    static boolean[][] vis;

    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());
        vis = new boolean[n][n];

        dfs(0, 0, n);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j]) {
                    bw.write("*");
                } else {
                    bw.write(" ");
                }
            }
            bw.newLine();
        }

        bw.flush();
    }

    static void dfs(int sr, int sc, int n) {
        if (n == 1) {
            vis[sr][sc] = true;
            return;
        }

        dfs(sr, sc, n / 3);
        dfs(sr, sc + n / 3, n / 3);
        dfs(sr, sc + n / 3 * 2, n / 3);
        dfs(sr + n / 3, sc, n / 3);
        dfs(sr + n / 3, sc + n / 3 * 2, n / 3);
        dfs(sr + n / 3 * 2, sc, n / 3);
        dfs(sr + n / 3 * 2, sc + n / 3, n / 3);
        dfs(sr + n / 3 * 2, sc + n / 3 * 2, n / 3);
    }
}


2. 풀이 [C++]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <bits/stdc++.h>
using namespace std;

const int MX = 2187;
bool vis[MX][MX];

void dfs(int sr, int sc, int n) {
    if (n == 1) {
        vis[sr][sc] = true;
        return;
    }

    dfs(sr, sc, n / 3);
    dfs(sr, sc + n / 3, n / 3);
    dfs(sr, sc + n / 3 * 2, n / 3);
    dfs(sr + n / 3, sc, n / 3);
    dfs(sr + n / 3, sc + n / 3 * 2, n / 3);
    dfs(sr + n / 3 * 2, sc, n / 3);
    dfs(sr + n / 3 * 2, sc + n / 3, n / 3);
    dfs(sr + n / 3 * 2, sc + n / 3 * 2, n / 3);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    dfs(0, 0, n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (vis[i][j]) {
                cout << '*';
            } else {
                cout << ' ';
            }
        }
        cout << '\n';
    }
}

3. 디버깅


없음.

4. 참고


없음.

PS, BaekJoon
Unlinked
This post is licensed under CC BY 4.0 by the author.