[Python] 15649 : N과 M (1)

# 링크

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

---

# 문제

---

# 접근

• N개의 숫자중 M개를 골라 순열을 만드는 문제입니다
• itertools의 permutations 모듈을 사용하면 풀 수는 있지만 학습적인 측면에서 큰 의미는 없습니다
• 숫자를 하나 고르고 남은 숫자중 또 하나를 고르고 남은 숫자중 ...
• 길이가 M인 수열이 완성되면 출력하고, 하나 지우고 다른 하나를 다시 선택하러 들어가는
• 재귀함수로 작성하였습니다

---

# 코드

# 외부모됼
# from itertools import permutations
# N, M = map(int, input().split())
# arr = list(range(1, N+1))
# print(list(permutations(arr, M)))

# dfs 재귀로 구현
def dfs(x): # x는 숫자 고른 개수
    if x == M: # M개만큼 골랐으면
        print(*result) # 들어있는 순열 언패킹
        return # 해당 재귀 종료
    
    for i in range(N): # 재귀를 통해, N개중 하나 -> N-1개중 하나 -> N-2개중 하나 ...
        if visited[i]: # 이미 고른 수이면
            continue

        result.append(arr[i]) # 하나 고르고
        visited[i] = 1 # 방문처리 하고
        dfs(x+1) # 다음 숫자 고르기
        result.pop() # 돌아와서 골랐던 숫자 빼고
        visited[i] = 0 # 방문 취소하고

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

arr = list(range(1, N+1))

visited = [0] * N

result = []

dfs(0) # 고른 숫자 0개부터 시작

---

# 정리

• 가장 기본적인 DFS로 순열을 구현하는 코드입니다
• 기존에 알고 있던 순열만드는 코드는 N개의 숫자중 N개로 구성된 순열밖에 만들지 못했는데
• 이번 문제를 공부하면서 N개의 숫자중 M개로 구성된 순열을 만들어보게 되었습니다
• DFS는 여전히 감이 오지 않습니다만
• 출발 -> 종료조건확인 -> 한 단계 진입 -> DFS -> 진입 취소
• 의 과정으로 코드가 작성되는 맥락을 대강 이해하였습니다
• 완전히 백지상태였던 DFS도 어찌저찌 문제를 풀다보니 한 10%쯤 이해가 된 것 같습니다
• 비슷한 문제를 50개 정도 풀고나면 DFS를 비교적 자유롭게 사용하게 될 수 있을 것 같습니다