본문 바로가기
알고리즘/백트래킹

[백준-실버2] 15664번 N과 M(10) (백트래킹, 파이썬)

by 호리미 2022. 2. 7.

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)