[ETC] 원의 방적식을 이용한 별찍기

최근 접했던 문제 중에 원의 방정식을 이용한 문제가 있었다. 

지인의 급한일을 주말동안 도와주는 상황에서도 계속 머릿속에 맴돌아서 어떻게 구현할지 고민하면서 쉴 때마다 메모장에 구현 방법을 생각해보았는데  결론적으로는 난이도가 쉬운 문제여서 뭔가 김빠지는 느낌이있었지만 그 내용을 남긴다.

 

처음에 구현을 할때 고려했던 것은 원의 방정식의 구성이었다. 

(x-a)^2 +(y-b)^2 = r^2 이 기준이고 기준점이 되는 a와 b의 개념이 있지만 모양을 만드는 것에만 집중해도 되었기 때문에 이 내용은 뺀다고 생각하여 x^2 +y^2 = r^2 을 사용하려고 생각하였다.

그리고 두 변수의 표현을 2중 for문을 이용하여 순회하면서 체크하면서 된다고 생각하였다.

 

그리고 2중 for문의 i 와 j를 각각 x와 y에 대입하고 처음에 파라미터로 전달받는 상수값을 원의 크기 값으로 생각하여 같은 값이 나오는 부분에는 *을 배열 안에 넣어주고 이 별이 한 행에서 두 번 나올 경우 처음 시작과 끝을 start flag를 만들어서 두 번째 같은 값이 나올 때까지 별을 찍는 방식으로 구현하였지만 결과는 원하는 값이 나오지 않았다.

 

위에 전제가 된 내용들은 잘못된 오류가 너무 많았는데 결과값이 찍힌 것을 보면서 이해하게 되었다.

 

- 처음 생각해본 솔루션

def solution(size):
    board = [[' '] * (size + 1) for _ in range(size + 1)]
    r_circle = int(size / 2)

    for i in range(-size, size):
        start = 0
        for j in range(-size, size):
            if (i ** 2) + (j ** 2) == r_circle ** 2:
                board[i + r_circle][j + r_circle] = '*'
                if start == 0:
                    start = 1
                else:
                    board[i][j] = '*'
                    start = 0
            if start == 1:
                board[i][j] = '*'


    for bo in board:
        print(*bo)

    return board

solution(20)

 

잘못된 내용을 다시 생각해보니 i와 j가 일정한 상수값에 의해서 움직이면서 2중 배열의 특정 행에서는 원하는 값이 없는 곳이 있어서 완전히 비어있는 배열이 나올 수 있다는 점등 자잘한 문제들이 있었다. 아무래도 원으로 이루어진 각각의 점들을 배열의 특정값과 같을 것이라는 전제하에서 만들었던 솔루션이라 문제가 있다고 생각하였고 이를 해결하기 위하여 중간에 사용한 start flag에 관한 내용은 빼고 같을 때가 아니고 방정식 안쪽에 들어갈 때를 가정하여 코드 수정을 하였다 해당 내용은 밑과 같다.

 

- 최종 솔루션

def solution(size):
    board = [[' '] * (size + 1) for _ in range(size + 1)]
    r_circle = int(size / 2)

    for i in range(-size, size):
        for j in range(-size, size):
            if (i ** 2) + (j ** 2) <= r_circle ** 2:
                board[i + r_circle][j + r_circle] = '*'

    for bo in board:
        print(*bo)

    return board


solution(20)

알고리즘 공부 처음 시작하였을 때 백준에서 별을 찍는 문제를 많이 풀어보았지만 오랫만에 다시 풀어보니 뭔가 재밌는 문제였다.