백준 알고리즘 6603번: 로또 (Python)

문제 정보

---

6603번: 로또

 

 

핵심

---

백트래킹, DFS를 사용하여 풀이할 수 있는 문제이다

조합 문제기 때문에, 파이썬의 라이브러리인 combinations 을 사용하여 풀이할 수 있지만 대부분의 코딩 테스트에서 이와 같은 라이브러리를 허용해 주지 않을 확률이 높기 때문에 정석적인 풀이로 풀어보았다

풀이 시간은 조금 걸렸고, DFS 문제가 거의 처음이거나 풀이한 지 많이 오래 되었기 때문에 그런 것 같다

 

풀이

---

import sys

def DFS(L, startWith):
    if L == 6:
        print(' '.join(str(i) for i in tmp))
    else:
        for i in range(startWith, len(S)):
            tmp[L] = S[i]
            DFS(L+1, i+1)


commands = sys.stdin.read().splitlines()

for command in commands:
    if command == '0':
        exit()
    S = list(map(int, command.strip().split(' ')[1:]))
    tmp = [[] for _ in range(6)]
    DFS(0, 0)
    print()

먼저 L은 Level (Depth) 이다.

L이 6이 되면 (k개 중 6개를 고르는 조합 문제이기 때문) 해당 집합을 출력해 준다

아니라면, 해당 수를 배열에 추가하고 다음 수를 추가를 위한 재귀호출을 실시해 준다

 

주어진 집합이 다음과 같을 때 7C6 의 계산이 이루어지게 되는데,

1 2 3 4 5 6 7

중복을 허용하지 않기 때문에 이전 인덱스의 수보다 더 커질 순 없다

1 2
2 1 (X)

그렇기에 위 코드의 DFS 부분에서

DFS(L+1, i+1)

Level을 1씩 올림과 동시에, startIndex 또한 올려주는 것이다

 

고찰

---

combinations 를 활용한 풀이는 다음과 같다.

from itertools import combinations
while 1:
    k,*s = map(int,input().split())
    if k == 0 : break
    for c in combinations(s,6): print(*c)
    print()

하지만 앞서 말한대로, 라이브러리의 제한이 있을 수 있는 상황에서 풀이하려면 정석적인 풀이를 공부하는게 좋다는 생각을 하였다

 

참고

---

GitHub - dduneon/CodingTestPy

해당 README 파일을 참고하면 위 소스코드를 볼 수 있다