[Baekjoon Online Judge] 백준 6603번 로또(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 6603번 로또

(Python)

(글쓴날 : 2020.03.24)

 

---

* Baekjoon Online Judge, 백준 6603번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 6603번 로또

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/6603

6603번: 로또

---

2) 풀이 과정

로또 번호의 집합이 주어졌을 때 그 속에서 최대 6개의 조합을 구하는 문제입니다.

조합이란 순서를 고려하지 않은 부분집합을 의미합니다.

 

저의 경우, DFS와 백트래킹을 이용해 문제에 접근했습니다.

번호를 탐색했는지 확인하기 위한 visit 리스트와 선택된 번호들을 저장해 놓을 printList 리스트를 생성하고, backTracking() 함수에 시작 index인 0, 집합 S, visit 리스트, printList를 인자로 넘깁니다.

 

backTracking() 함수 내부에서 반복문을 돌려 로또 번호를 차례대로 탐색해가며 만약 처음 탐색됐을 시 printList 리스트에 저장한 후 다시 backTracking() 함수를 재귀 호출합니다.

그렇게 반복하다 만약, printList 리스트의 길이가 6이 되면 저장되어 있던 번호들을 출력하고 회귀합니다.

회귀된 후 printList에서 가장 마지막에 저장된 번호를 pop() 함수로 제거한 후 해당 index의 visit 리스트에 False를 저장하여 탐색하지 않았다고 표시합니다. (백트래킹 구현 방식입니다.)

 

문제에서 집합의 원소들이 오름차순으로 주어질 뿐만 아니라, 출력 역시 오름차순으로 해야 되기 때문에 재귀 호출을 하기 전의 반복 제어 값을 인자로 넘겨 재귀 호출된 backTracking() 함수 반복문의 시작 값으로 설정하면 불필요한 반복을 하지 않게 되므로 시간 효율을 높일 수 있습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def backTracking(index, S, visit, printList):
    if len(printList) == 6:
        print(*printList)
        return
 
    for i in range(index, len(S)):
        if not visit[i]:
            visit[i] = True
            printList.append(S[i])
            backTracking(i, S, visit, printList)
 
            printList.pop()
            visit[i] = False
 
 
while True:
    case = list(map(int, input().split()))
    k = case[0]
    if k == 0:
        exit()
 
    S = case[1:]
 
    printList = []
    
    visit = [False] * len(S)
    backTracking(0, S, visit, printList)
    print()

---