백준 알고리즘 15649 (N과 M(1)) - python (재풀이)

백준 알고리즘 15649 (N과 M(1)) - python

> https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

백트래킹의 기본 문제.

1~N까지 자연수 중 길이가 M인 중복되지 않는 수열 출력

 

[문제 풀이]

1. depth가 늘어날 때마다 배열을 저장해 줄 result 생성

2. 알아보기 쉽게 (N+1) size로 하여 자연수 값 그대로 적용되게 함

3. DFS 탈출 조건 : 길이(이 문제는 depth로 생각해도 됨)가 M을 만족

4. 저장된 result 배열을 ' ' 공백으로 합쳐서 출력

5. 백트래킹을 하며 depth+1 값을 제거처리해줌

6. 결과적으로 가장 깊은 depth 부터 교체되며 결과가 출력됨 

 

[Code]

import sys
# N까지 자연수 중 길이가 M인 수열 (중복X)
def DFS(depth):
    if depth == M:  # 탈출 조건
        print(' '.join(map(str, result)))
        return  # 탈출
    else:
        for n in range(1, N+1):  # 탐사 범위
            if not visited[n]:  # 탐사 안했다면
                visited[n] = True  # 체크
                result.append(n)  # 결과 저장
                DFS(depth+1)  # 계속 진행
                visited[n] = False  # 백트래킹 탐사 안한 처리
                result.pop()  # depth 유지하고 depth+1 값 제거
    return

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    result = []  # 출력 내용
    # 탐사 여부, 보기 쉽게 자연수 size로 만들어 줌
    visited = [False] * (N + 1)  
    DFS(0)