백준 15649번 파이썬 풀이

우선 정답입니다

 

n, m = map(int, input().split())
visited = [False] * (n + 1)  # 방문 여부를 저장할 리스트
result = []  # 수열을 저장할 리스트

def dfs(cnt):
    if cnt == m:  # M개의 수열을 모두 선택한 경우
        print(' '.join(map(str, result)))  # 리스트를 문자열로 변환하여 출력
        return

    for i in range(1, n + 1):
        if not visited[i]:
            visited[i] = True  # 수 선택
            result.append(i)  # 선택한 수를 결과 리스트에 추가
            dfs(cnt + 1)  # 다음 숫자를 선택하러 이동
            visited[i] = False  # 수 선택 해제
            result.pop()  # 마지막에 추가된 수 제거

dfs(0)  # DFS 함수 호출

주어진 자연수 N과 M을 이용하여 1부터 N까지의 자연수 중에서 중복 없이

M개를 고른 수열을 모두 출력하는 것입니다.

이 문제는 백트래킹 알고리즘을 사용하여 해결할 수 있습니다.

 

백트래킹 알고리즘은 모든 가능한 경우의 수를 시도하면서 해를 찾아가는 알고리즘입니다.

이 알고리즘은 DFS(Depth-First Search) 기반으로 동작합니다.

백트래킹 알고리즘은 모든 가능한 경우의 수를 찾는 것이 아니라,

현재 상태에서 가능한 모든 경우를 시도해보고, 문제의 조건에 맞지 않는 경우

그 이후의 시도는 하지 않고 되돌아갑니다.

 

이를 통해 불필요한 시도를 줄이고, 시간과 공간을 절약할 수 있습니다.

알고리즘의 구현 방법은 다음과 같습니다.

1. 수열을 저장할 리스트와 방문 여부를 저장할 리스트를 초기화합니다.
2. 백트래킹 알고리즘의 기본 형태인 DFS 함수를 구현합니다. DFS 함수는 현재까지 선택한 수열과 방문 여부 리스트, 선택한 숫자의 개수를 인자로 받습니다.
3. 만약 선택한 숫자의 개수가 M과 같다면, 현재까지 선택한 수열을 출력합니다.
4. 아직 M개의 수열을 선택하지 않았다면, 1부터 N까지의 자연수 중에서 아직 선택되지 않은 수를 찾아서 선택합니다.
5. 선택한 수의 방문 여부를 체크하고, DFS 함수를 재귀적으로 호출합니다.
6. DFS 함수가 리턴될 때, 선택한 수의 방문 여부를 체크 해제합니다.

 

 

[대표이미지]