[Baekjoon Online Judge] 백준 15650번 N과 M (2)(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 15650번 N과 M (2)

(Python)

(글쓴날 : 2020.04.02)

 

---

* Baekjoon Online Judge, 백준 15650번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 15650번 N과 M (2)

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

---

2) 풀이 과정

자연수 N과 M이 주어질 때, 길이가 M인 1부터 N까지의 조합을 구해 오름차순으로 출력하는 문제입니다.

 

저의 경우, DFS를 적용하여 문제에 접근했으며, 조합을 구해야 하기 때문에 DFS() 함수를 호출할 때 인자로 탐색 반복문의 index를 넘겨 깊이 우선 탐색을 실시해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def DFS(index):
    global N, M, nums, visit, stack
 
    if len(stack) == M:
        print(*stack)
        return
 
    for i in range(index, N):
        if not visit[i]:
            visit[i] = True
            stack.append(nums[i])
            DFS(i)
            visit[i] = False
            stack.pop()
 
 
N, M = map(int, input().split())
nums = [i for i in range(1, N + 1)]
visit = [False] * N
stack = []
 
DFS(0)

---