시리즈 12번 코드
import sys
n, m = map(int, sys.stdin.readline().strip().split())
origin = list(map(int, sys.stdin.readline().strip().split()))
origin.sort()
answer = []
check=[0]*n
def dfs(cnt,idx):
if cnt == m:
for ans in answer:
print(ans,end = ' ')
print("",end = '\n')
return
temp = 0
for i in range(idx,n):
if check[i]==m or temp==origin[i]:
continue
check[i]+=1
temp = origin[i]
answer.append(temp)
dfs(cnt+1,i)
check[i]-=1
answer.pop()
dfs(0,0)계수의 범위로 할 수 없을 경우 check를 숫자 자체에 대해 하기보다 idx로 한다
checkidx[i]
중복을 고려하는 경우 :: m개까지는 뽑아내겠다
for문 내 check[i] == m:
continue
오름차순 고려 ::
for문 내 dfs(cnt+1, i+1)
동일 요소가 있을 때, 중복된 깊이 우선탐색을 피하는 방법 ::
temp = 0
for i in range(n):
temp == origin[i] >> continue 처리
~~~ temp = origin[i]
예시 : 1,7,9,9,11 수열에서 3개의 수열 뽑아낼 경우
1,7,9
1,7,9 (X)
1,7,11
1,9,9
1,9,11
1,9,11 (X)
'''
1,7이나 1,9 깊이까지 갔을 경우 자신과 같은 모든 경우를 다 탐색했을 것이기 때문에
다른 7이나 9의 경우에 생각할 필요가 없다
dfs특성상 1개의 스택만 담으면 바로 다음 함수가 호출되므로,
자신의 벡터끼리만 비교해서 중복되는 벡터면 continue라는 것이 핵심
내 실수 : 담는 주체(stack의 top)와 벡터가 같으면 문제가 있다고 생각하고 구현했음.
ㄴ>이렇게 하면 1,9,9는 담을 수가 없도록 된다.
벡터간의 중복만 따져야한다.
42Seoul