[알고리즘/백트래킹] 15654번 : N과 M(5) - python

링크 : https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

---

• 문제
• 소요시간: 4분 35초

---

• 설계하기(접근방법) 

1. 입력받기

n, m 과

수열을 입력받는다

 

2. 구현하기

이전의 백트래킹은

1 ~ n까지 순회하였다면

 

이번 문제는 주어진 리스트 자체를 순회하면 된다

for i in num_list로 순회해서

해당 순열만 ans에 append 한다

 

3. 출력하기

ans를 출력한다

---

• 코드(출력)

n, m = map(int, input().split())

num_list= list(map(int, input().split()))
num_list.sort()
max_num = max(num_list)
ans = []
visited = [0 for _ in range(max_num + 1)]

def dfs(cnt,lst):
    if cnt == m:
        ans.append(lst)
    else:
        for i in num_list:
            if visited[i] == 0:
                visited[i] = 1
                dfs(cnt + 1, lst + [i])
                visited[i] = 0
dfs(0, [])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 정해진 1 ~ n까지가 아닌 주어진 숫자들만 순회했다