[BaekJoon] "DFS/BFS" - 백준 6603번 문제 : 로또

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

6603번: 로또

 

- 독일 로또는 1~49에서 수 6개를 고름

입력으로 주어지는 숫자 그룹 중에서 6개를 선택하는 모든 경우의 수 출력

 

[해결 로직]

- 이것도, DFS 즉 재귀를 사용하면 됨

- 근데 다른게 뭐냐면, 여기는 중복이 허용이 안되기 때문에 dfs 함수 내에 인덱스를 계속 +1해줘서 다음꺼를 탐색하게 해줘야 함

- 그렇지 않으면, 처음부터 재 탐색이라 똑같은 수를 중복으로 뽑게 됨

- 선택한 수들을 배열에 넣어주고, 그 배열의 길이가 6이면 출력

 

[Solution 코드]

totalinp = []

while True:
    inp = list(map(int, input().split()))
    totalinp.append(inp)
    if inp[0] == 0: ##  0 누르면 종료
        break


def dfs(k, graph, idx, sol):
    #print(sol)

    if len(sol) == 6:
        print(*sol)
        return


    for i in range(idx, len(graph)):
        sol.append(graph[i])
        dfs(k, graph, i+1, sol)
        sol.pop()




for i in range(len(totalinp)):
    dfs(totalinp[i][0], totalinp[i][1:], 0, [])
    print("")

 

재밌다 탐색