[코딩테스트 공부] N과M (1)

출처 : https://www.acmicpc.net/problem/15649

문제가 간단하니, 코드부터 일단 보겠습니다

# Problem 15649

# 재귀함수
def recursive_func(k, sequence):
    # 탈출 조건
    if(k == M):
        print(sequence)
        return
    
    # 점화 관계 (1부터 N 까지의 숫자 순회)
    for i in range(0, N):
        if(visited_list[i] == False):
            visited_list[i] = True
            sequence_param = sequence + str(i + 1) + " "
            recursive_func(k + 1, sequence_param)
            visited_list[i] = False

N, M = map(int, input().split(" "))
visited_list = [False] * N # 방문 리스트

recursive_func(0, "")

코드 해설

위 문제는, 한번 방문했던 숫자에 대해서는 다시 방문하지 않는 재귀함수 알고리즘을 작성해야합니다.

따라서, visit_list를 하나 두어서, 재귀함수가 도는 동안 특정 값이 이미 참조가 되었는지 검사를 시행합니다.

visited_list[i] = True
sequence_param = sequence + str(i + 1) + " "
recursive_func(k + 1, sequence_param)
visited_list[i] = False

위 부분이 좀 특이할 수도 있는데요, visit_list[i]를 True로 맞췄다가 이후에 False로 맞춘 이유는, for문에서 다음 i를 참조할 때, 그 인덱스에 방문했다는 기록을 지워줘야만 다음 k로 넘어갈 때 문제가 발생하지 않기 때문입니다. (재귀함수를 구현할 때, 이전의 상태를 소거시킨다! 라고 이해해도 괜찮겠죠?)

따라서, 위의 코드를 통해 우리는 원하는 결과를 얻어낼 수 있습니다.