https://www.acmicpc.net/problem/15664
15664번: N과 M (10)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
< 내 코드>
- N과 M(9)번 문제는 순서를 고려했지만, 이번 문제는 순서를 고려하지 않는다.
--> (1 7 <--> 7 1 중 1 7만 허용함)
- 따라서 dfs에 start 파라미터를 이용하여 중복을 제거했다.
- 나머지는 N과 M 9번문제랑 같으니 참고할 것
- https://it-hyorim.tistory.com/93
[백준-실버2] 15663번 N과 M(9) (백트래킹, 파이썬)
https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
it-hyorim.tistory.com
#n과 m 9번
import copy
n, m = map(int, input().split())
nums = list(map(int, input().split())) #중복 제거
#nums.sort() 마지막에 set에 넣을거라 미리 정렬 안해도됨
stack = []
visited = [False]*n
result = []
def dfs():
global result, stack
if len(stack) == m:
s = copy.deepcopy(stack) ## 이 부분 주의
result.append(s)
return
for i in range(n):
if visited[i] == False:
visited[i] = True
stack.append(nums[i])
dfs()
stack.pop()
visited[i] = False
dfs()
result = sorted(list(set(list(map(tuple, result))))) #셋은 순서가 없어서 정렬 망가짐
for r in result:
print(*r)
'알고리즘 > 백트래킹' 카테고리의 다른 글
[백준-실버2] 15666번 N과 M(12) (백트래킹, 파이썬) (0) | 2022.02.07 |
---|---|
[백준-실버2] 15665번 N과 M(11) (백트래킹, 파이썬) (0) | 2022.02.07 |
[백준-실버2] 15663번 N과 M(9) (백트래킹, 파이썬) (0) | 2022.02.07 |
[백준-실버3] 15657번 N과 M(8) (파이썬, 백트래킹, DFS) (0) | 2022.02.06 |
[백준-실버3] 15656번 N과 M(7) (파이썬, 백트래킹, DFS) (0) | 2022.02.06 |