[백준] 2448번 : 별찍기 - 11 (파이썬)

재귀, 분할정복 문제

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

 

접근 방식

 

별은 위와 같이 n // 2로 분할해도 같은 형상을 갖는다. 즉, 특정 패턴이 반복되어 나타내는 것을 볼 수 있다.
이는 전형적인 분할정복 문제의 특징이다. 분할정복 문제는 재귀로 풀면 쉽게 풀리므로 나 또한 재귀로 접근해겠다.

 

 

💡 풀이코드 (성공)

import sys
n = int(sys.stdin.readline())

graph = [[' '] * n * 2 for _ in range(n)]

def star(n, r, c):
    if n == 3:
        graph[r][c] = '*'
        for j in range(c - 1, c + 2):
            if j == c: continue
            graph[r + 1][j] = '*'
        for j in range(c - 2, c + 3):
            graph[r + 2][j] = '*'

    else:
        newSize = n // 2
        # center = newSize * 2 - 1
        star(newSize, r, c) # 1
        star(newSize, r + newSize, c - newSize) # 2
        star(newSize, r + newSize, c + newSize) # 3
star(n, 0, n - 1)
print(graph)
for i in graph:
    print(''.join(i))

 

👩🏻‍💻 위의 코드

• 2n x n으로 2차원 배열을 생성한다. 초깃값은 ' '(공백)이다.
• star (재귀호출할 함수)
  • 한 변의 길이를 나타내는 n과 어느 위치에 별을 출력할지를 나타내는 r, c를 인자로 받는다.
  • base condition (n = 3) : 더이상 쪼갤 수 없으므로 인자로 받은 r,c의 위치(graph[r][c])에 ' '을 '*'의 값으로 치환한다.
  • n = 3에서 다음과 같은 형태의 별을 찍어야 하는데, 인자로 넘겨받은 r,c은 첫번째 줄에서 '*'(별 하나)의 좌표값을 의미한다.

• 문제에선 트리 모양의 별들의 3개의 형태로 반복패턴이 나타난다. 따라서, 우리는 3번의 재귀호출 패턴을 만들 것이다.
• star(분할하여 재귀 호출할 새로운 크기, 트리의 첫번째 줄의 row, 트리의 첫번째 줄의 column)
  우리는 다음과 같이 해당 트리에서 첫번째 줄의 row, column 값만 알면 분할을 계속적으로 하여 base condition에서 별을 출력할 수 있게 된다.

star(newSize, r, c) # 1
star(newSize, r + newSize, c - newSize) # 2
star(newSize, r + newSize, c + newSize) # 3

 

 

참고문헌

https://hongcoding.tistory.com/90

[백준] 2448 별 찍기 - 11 (Python 파이썬)