15663
날짜 : 2023. 08. 31
사용 언어 : python
문제
코드
import sys
n, m = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()
res = list()
visited = [False] * n
def bt(depth):
if depth == m:
print(*res)
return
prev = 0
for i in range(n):
if not visited[i] and prev != nums[i]:
prev = nums[i] # 수열의 최신 원소
visited[i] = True # 방문처리
res.append(prev)
bt(depth + 1)
visited[i] = False
res.pop()
bt(0)
풀이
- DFS를 활용한 백트래킹을 사용해 문제를 풀이한다.
- 다만 중복이 되지 않는 수열을 만들어야 하기 때문에 앞서 숫자들을 입력받고 sort를 실행하여 재귀를 실행한다.
- 또한 같은 depth에서 동일한 값의 element가 기준이 되는 것을 방지하기 위해 이전값을 저장하기 위한 용도로 prev변수를 설정하고, 그 값을 저장하여 중복을 방지한다.
알게된 점
- 먼저 depth에 해당하는 수열들을 하나의 set에 저장한 후에 값들을 출력하려 했지만 set에는 리스트가 원소로 존재할 수 없었다.
- 그 다음 방법으로는 리스트를 미리 만들어서 depth에 해당하면 출력하는 방식으로 하려고 했지만 파이썬 언어 특성상 재귀 단계에 따라서 값이 계속 유동적으로 변화하는 속성이 있었기 때문에 원하는 결과가 나오지 않았다.
- 그래서 깊은복사로 문제를 풀어보려 했지만 동일한 값을 같은 depth에서 기준으로 잡았을 때의 케이스를 걸러낼 수 없어서 계속 오답이 나왔다.
- 때문에 다른사람들의 풀이를 참고했고, prev의 사용방식을 알 수 있었다. 처음에는 왜 이렇게 사용할까 의문이 들었지만, 직접 DFS 트리를 그려보고 로직을 따라가보니 해당 노드의 기준을 잡았을 때 prev를 잡는 이유를 확인할 수 있었다.
- 취업하고 오랜만에 코테를 풀어봤는데 감이 많이 떨어진 것 같다;; 최대한 꾸준히 풀면서 다시 감을 익혀나가야겠다.
참고 사이트
-