백준 4779번 - 칸토어 집합 - 파이썬(Python)

문제 링크

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

문제

칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다.

전체 집합이 유한이라고 가정하고, 다음과 같은 과정을 통해서 칸토어 집합의 근사를 만들어보자.

1. -가 3N개 있는 문자열에서 시작한다.

2. 문자열을 3등분 한 뒤, 가운데 문자열을 공백으로 바꾼다. 이렇게 하면, 선(문자열) 2개가 남는다.

3. 이제 각 선(문자열)을 3등분 하고, 가운데 문자열을 공백으로 바꾼다. 이 과정은 모든 선의 길이가 1일때 까지 계속 한다.

예를 들어, N=3인 경우, 길이가 27인 문자열로 시작한다.

---------------------------

여기서 가운데 문자열을 공백으로 바꾼다.

---------         ---------

남은 두 선의 가운데 문자열을 공백으로 바꾼다.

---   ---         ---   ---

한번 더

- -   - -         - -   - -

모든 선의 길이가 1이면 멈춘다. N이 주어졌을 때, 마지막 과정이 끝난 후 결과를 출력하는 프로그램을 작성하시오.

입력 조건

• 입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.

출력 조건

• 입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

 

입력 예시

0
1
3
2

출력 예시

-
- -
- -   - -         - -   - -
- -   - -

 

풀이 전 생각

 문제에서 '모든 선의 길이가 1이면 멈춘다'는 조건과 '3등분한 것을 기준으로 왼쪽과 오른쪽 덩어리를 반복해서 3등분'한다는 규칙을 이용해서 end-start(3등분할 지점의 끝-3등분할 지점의 시작)==1을 베이스 조건(재귀의 종료 조건)으로 정하고, 3^N 길이를 가진 배열을 만들어 배열의 인덱스를 이용해 가운데를 잘라주는 것을 반복하면 될 것 같다.

 

예제 코드

def cantore(start,end):
    third_1=(end-start)//3  #인덱스x, 칸수!!!
    third_2=third_1*2
    if end-start == 1:
        return
    list[start+third_1:start+third_2]=[' ']*third_1
    cantore(start,start+third_1)
    cantore(start+third_2,end)
while True:
    try:
        n=int(input())
        str_len = 3**n
        list = ['-']*str_len
        cantore(0,str_len)
        print(''.join(list))
    except:
        break

 

포인트

 이 문제의 입력 예시와 출력 예시를 보면 일반적인 문제들과는 다르게 입력 하나당 출력 하나가 나오는 것이 아니라 계속해서 입력을 받고, 출력 결과를 보여주는 방식으로 작성을 해야한다. 

이때 while 문과 try except 구문을 사용하여 EOF에러를 해결해주는데 EOF에 관해서는 나중에 정리해서 *링크달 것*

 

 

생각

 처음 코드를 작성할 때는 third_1,third_2가 인덱스이자 칸수를 나타내는 것으로 착각하고 코드를 작성했다. 하지만 이 변수들이 인덱스로 사용될 수 있는 경우는 재귀함수를 호출하기 전에만 해당되고 재귀함수를 호출한 후에는 시작지점과 끝지점을 3등분했을 때 각각 첫번째와 두번째 칸수라는 것인데, 이 실수를 알아차리는 데 꽤 오랜 시간이 걸렸다. 

 그리고 문제를 풀면서 재귀함수의 호출 순서에 대해서 헷갈리는 부분이 있었는데, 이 부분을 아래와 같이 시각화하고 코드가 실행되는 순서에 따라 변수값들이 변하는 과정을 보면서 재귀를 조금 더 깊이 이해하게 되었다. 재귀함수를 공부하기 위해서 구글링했을 때 보통 팩토리얼이나 피보나치정도의 내용이 나오는데 사실 그 정도 내용을 이해하고 나서 난이도 있는 재귀 문제들을 풀기에는 많이 버거웠다. 이번에 작성한 코드에서는 cantore가 두번 반복해서 나오는 부분이 있다. 이때 첫번째 cantore를 재귀적으로 호출하다가 return을 하게 되는 지점에서 반대로 스택에 쌓인 재귀함수를 실행을 하게 되는데 팩토리얼,피보나치와 다르게 함수 내에서 변경된 변수값을 다시 인자로 넣어주는 부분이 추가되어 있어 조금 더 깊이 있는 이해가 가능할 것 같다. 나중에 혹시 재귀 내용을 따로 정리하게 되면 이 문제를 넣어야겠다. 

3을 입력했을 때, 재귀함수 호출 순서

참고자료

https://pythontutor.com/render.html#mode=display

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java

위 사이트에 아래 내용을 입력하고 실행하면 위 사진처럼 시각화가 가능하다.

def cantore(start,end):
    print(''.join(list))
    third_1=(end-start)//3
    third_2=third_1*2
    if end-start == 1:
        return
    list[start+third_1:start+third_2]=[' ']*third_1
    cantore(start,start+third_1)
    cantore(start+third_2,end)
while True:
    try:
        n=int(input())
        str_len = 3**n
        list = ['-']*str_len
        cantore(0,str_len)
        print(''.join(list))
    except:
        break