백준 6603 : 로또

dfs 개념이 활용된 문제이다.

---

처음에는 아래와 같이 깊이를 의미하는 d를 추가를 안했다.

그런데 아래와 같이 하면 idx를 층으로 쓴다는 얘기인데 그렇게 되면 '층'을 의미하는 원소와, '값(크기)'을 의미하는 원소간 의미 구분이 안된다.

 

import sys

def ans(idx):
    if idx >= 7:
        print(*res)
        return 0
    for i in range(idx, t[0] + 1):
        res.append(t[i])
        ans(i + 1)
        res.pop()

while 1:
    t = [*map(int, sys.stdin.readline().split())]
    res = []
    if t[0]:
        ans(1)
    else:
        break

 

그래서 '값(크기)'이 커져버리면 현재 '층' 수가 높은 것으로 착각되면서 탐색이 중간에 끊겨버린다.

그래서 아래와 같이 바꿨다.

 

import sys

def ans(idx, d):
    if d == 7:
        print(*res)
        return 0
    for i in range(idx, t[0] + 1):
        res.append(t[i])
        ans(i + 1, d + 1)
        res.pop()

while 1:
    t = [*map(int, sys.stdin.readline().split())]
    res = []
    if t[0]:
        ans(1, 1)
    else:
        break
    print()

 

이제는 '층' 개념을 추가해줬기 때문에 6층을 탐색하면서 '값' 에 해당하는 인덱스가 높아지더라도 현재 탐색중인 층과 헷갈리지 않는다.

---

중간에 '이거 dfs 문제구나.' 하고 감으로 맞춘 순간이 있긴 했는데, 그 때 그냥 안넘어가고 모르는 부분 확실하게 짚고 넘어가니까, 내가 모르는게 정확히 뭔지와 dfs의 활용법에 대해 더 깊이 이해하게 된 것 같다.