[Baekjoon Online Judge] 백준 15652번 N과 M (4)(Python)

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

[Baekjoon Online Judge] 백준 15652번 N과 M (4)

(Python)

(글쓴날 : 2020.04.02)

 

---

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

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

---

 

 

백준 15652번 N과 M (4)

---

1) 문제

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

15652번: N과 M (4)

---

2) 풀이 과정

자연수 N과 M이 주어질 때, 길이가 M인 1부터 N까지의 중복 조합을 구하거나, 비내림차순인 중복 순열을 구해 출력하는 문제입니다.

 

저의 경우, DFS를 적용하여 문제에 접근했으며, 두 가지 방식으로 문제를 해결했습니다.

 

첫 번째 방식은 중복 조합을 구하여 해결했고, DFS() 함수를 호출할 때 인자로 탐색 반복문의 index를 넘겨 깊이 우선 탐색을 실시하며, 만약 스택의 길이가 M이 되면 회귀하는 조건을 설정하여 백트래킹으로 문제를 해결했습니다.

 

두 번째 방식은 비내림차순인 중복 순열을 구하여 해결했고, DFS() 함수 내에 스택에 넣을 값이 이전에 넣은 값보다 작은 값이면 탐색을 하지 않는 조건과 만약 스택의 길이가 M이 되면 회귀하는 조건을 설정하여 백트래킹으로 문제를 해결했습니다.

 

아래의 코드에 두 가지 방식 모두 작성해놨으니 한번 비교해 보시면 좋을 것 같습니다.

---

3) 코드

 

* Python 코드(중복 조합)

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

---

* Python 코드(비내림차순 중복 순열)

import sys
input = sys.stdin.readline
 
def DFS(backNum):
    global N, M, nums, stack
 
    if len(stack) == M:
        print(*stack)
        return
 
    for i in range(N):
        if len(stack) and stack[-1] > nums[i]:
            continue
        stack.append(nums[i])
        DFS(nums[i])
        stack.pop()
 
N, M = map(int, input().split())
nums = [i for i in range(1, N + 1)]
stack = []
 
DFS(0)

---