[Baekjoon 15650 / Python / 실버3] N과 M (2)

문제

테스트 케이스

 

# 우선 모든 경우의 수 수열을 만드는 코드를 짠다

# depth가 0일 땐 바로 재귀 돌린다

# depth가 0이 아니라면 "이전 숫자와 비교해 더 클 경우" 재귀 돌린다

# num은 str 형태로 전달되며, 비교할 때만 int로 변환해 비교한다

# 수열이 완성되면 str형태의 num을 중간에 공백을 추가해서 result 리스트에 담는다

# result 리스트의 완성된 수열들을 차례로 출력한다

import sys

input = sys.stdin.readline

# 1 ~ N 까지의 수 / M개를 고른다

N, M = map(int, input().split())

visited = [False] * (N + 1) # 수와 인덱스를 맞추기 위해 + 1 한다

result = []

# 조건 검사 함수

def compare(a, b):

    if a > b:

        return False

    return True

def backTracking(depth, num):

   

    # 수열이 완성되었다면 result에 넣기

    if depth == M:

        result.append(' '.join(num))

        return

   

    for i in range(1, N + 1):

        if not visited[i]:

            if depth == 0 or compare(int(num[-1]), i):

                visited[i] = True

                backTracking(depth + 1, num + str(i))

                visited[i] = False

backTracking(0, '')

for re in result:

    print(re)

 

무난한 백트래킹 연습 문제이다. 어제 풀었던 부등호 문제와 조건이 유사해서 비교적 쉽게 풀 수 있었다.

 

num 변수를 이용해 조건을 통과할 때마다 수열을 추가했다. 뒤에 오는 숫자가 더 커야 하므로, 수를 비교하는 compare 함수를 따로 만들어 사용했다.

num 변수엔 숫자가 str 형태로 저장되어 있으며, compare함수로 비교할 때만 int 형태로 변환해 비교한다.

수열이 완성되면(최대 depth에 도달하면) join으로 수열 사이사이에 공백을 추가해 result 리스트에 저장한 후, 반복문으로 차례대로 출력한다.