[백준] 6603 - 로또 (python 파이썬)

백준 6603 문제 바로가기

풀이 코드

import sys

input = sys.stdin.readline


def comb(a, b):
    if a == 6:
        print(*order)
        return
    for i in range(b, k):
        order.append(lottos[i])
        comb(a + 1, i + 1)  # 재귀
        order.pop()  # 제거해가면 백트래킹 , 전 단계로 돌아감


while True:
    lottos = list(map(int, input().split()))
    k = lottos.pop(0)

    if not lottos:
        break

    order = []
    comb(0, 0)
    print()

dfs로 풀어야 하는 건 알았는데 생각보다 푸는데 오래 걸렸다 ...
백트래킹도 구글링을 통해서 알아보니깐 그래도 이해가 잘 된거같다!

6개가 되었을 경우 출력하고 맨 뒤의 수를 pop으로 제거하여 전 단계로 돌아가는 구조라고 이해했다.
그래도 이 문제는 코드를 조금 더 이해할 필요가 있는 문제! 스스로 아직 100% 이해는 아니기에...

회고

dfs는 뭔가 재귀를 통해 계속 탐색하면서 특정 조건?에 맞으면 탈출하는 그런식으로 풀고 있는데 아직 익숙하지는 않다... 이번주 주말에는 푼 문제들을 전부 코드를 지우고 다시 풀어봐야겠다!