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

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

15650번: N과 M (2)

 

---

• 문제
• 소요시간: 9분 23초

---

• 설계하기(접근방법) 

1. 입력받기

n,m 을 입력받는다

 

2. 구현하기

이전 문제와 구조는 비슷하다

 

마지막으로 리스트에 append 해줄 때

sort()를 한 후 ans 에 있는지 없는지 검사해준다

그러면 중복을 피할 수 있다

 

+++ 혹은

검사를 할 ㄸ

i부터 n까지가 아닌

이전에 append한 숫자를 인자로 넘겨서

apppend ~ n까지 순회하면

중복을 피할 수 있다

 

3. 출력하기

ans를 출력한다

---

• 코드(출력)

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

visited = [0 for _ in range(n + 1)]
ans = []

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

dfs(0, [])

for i in ans:
    print(*i)

---

• 얻어갈 부분

1. 백트래킹 응용을 했다