15663

날짜 : 2023. 08. 31

사용 언어 : python

 

문제

https://www.acmicpc.net/problem/15663

 

 

코드

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를 잡는 이유를 확인할 수 있었다.

- 취업하고 오랜만에 코테를 풀어봤는데 감이 많이 떨어진 것 같다;; 최대한 꾸준히 풀면서 다시 감을 익혀나가야겠다.

 

 

참고 사이트

-