[Python][백준 15650]N과 M (2)

문제

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

문제 풀이

앞서 풀었던 N과 M(1)과 유사한 문제이다.
조건 하나만 추가되었다.

✅ 수열을 사전 순으로 증가하는 순서로 출력하기 위해서는?

백트래킹 함수에서 숫자를 선택할 때, 선택된 숫자보다 큰 숫자만 선택하도록 조건을 추가해야 한다.

N과 M(1) 코드에서는 for 루프를 통해 1부터 N까지의 모든 숫자를 선택하고 있다.

def backtracking(n,m,selected,visited): #selected : 현재까지 선택된 수열 나타내는 리스트 
    # 수열의 길이가 m과 같아지면 selected 리스트의 내용을 출력하고 함수 종료 
    if len(selected) == m:
        print(' '.join(map(str,selected))) 
        return 

    for i in range(1,n+1):
        # 1부터 n까지의 숫자 중에서 방문하지 않은 숫자를 하나씩 선택 
        # 선택된 숫자를 selected 리스트에 추가하고, 방문으로 표시 
        if not visited[i]:
            visited[i] = True
            selected.append(i)
            # 재귀적으로 다음 숫자를 선택하기 위해 backtracking 함수 호출 
            backtracking(n,m,selected,visited)
            # 재귀 호출이 종료되면 선택한 숫자를 selected 리스트에서 제거하고
            # 해당 숫자를 방문하지 않았다고 표시 (다음으로 넘어가기 위함)
            selected.pop()
            visited[i] = False

n,m=map(int,input().split())

s=[] # 숫자가 쌓일 스택 
visited = [False] * (n+1) #방문 여부를 나타내는 리스트 visited 정의 
backtracking(n, m, [], visited,)

그러나 사전 순으로 증가하는 순서로 출력하기 위해서는 선택된 숫자 이후의 숫자들만 선택해야 한다.

정답 코드

# backtracking 함수의 인자에 start라는 변수가 추가. 
# 이 변수는 다음에 선택할 수 있는 숫자의 시작 위치를 나타낸다. 
# 기본적으로 start는 1로 초기화되며, 선택된 숫자보다 큰 숫자들만 선택할 수 있도록 
# 반복문의 범위를 range(start, N + 1)로 변경

def backtracking(n,m,selected,visited,start): #selected : 현재까지 선택된 수열 나타내는 리스트 
    # 수열의 길이가 m과 같아지면 selected 리스트의 내용을 출력하고 함수 종료 
    if len(selected) == m:
        print(' '.join(map(str,selected))) 
        return 

    for i in range(start,n+1):
        # 1부터 n까지의 숫자 중에서 방문하지 않은 숫자를 하나씩 선택 
        # 선택된 숫자를 selected 리스트에 추가하고, 방문으로 표시 
        if not visited[i]:
            visited[i] = True
            selected.append(i)
            # 재귀적으로 다음 숫자를 선택하기 위해 backtracking 함수 호출 
            # 재귀 호출 시에도 다음 숫자는 현재 선택한 숫자 i보다 큰 숫자부터 선택하도록 
            # backtracking(N, M, selected, visited, i + 1)으로 호출
            backtracking(n,m,selected,visited,i+1)
            # 재귀 호출이 종료되면 선택한 숫자를 selected 리스트에서 제거하고
            # 해당 숫자를 방문하지 않았다고 표시 (다음으로 넘어가기 위함)
            selected.pop()
            visited[i] = False

n,m=map(int,input().split())

s=[] # 숫자가 쌓일 스택 
visited = [False] * (n+1) #방문 여부를 나타내는 리스트 visited 정의 
backtracking(n, m, [], visited,1)

backtracking 함수의 인자에 start라는 변수가 추가되었다.

이 변수는 다음에 선택할 수 있는 숫자의 시작 위치를 나타낸다.

기본적으로 start는 1로 초기화되며, 선택된 숫자보다 큰 숫자들만 선택할 수 있도록 반복문의 범위를 range(start, N + 1)로 변경

재귀 호출 시에도 다음 숫자는 현재 선택한 숫자 i보다 큰 숫자부터 선택하도록 backtracking(N, M, selected, visited, i + 1)으로 호출