파이썬PS) 백준 6603 로또. 백트래킹

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

6603번: 로또

 

파이썬 PS) 백준 6603 로또. 백트래킹

 

알고리즘 - dfs를 이용한 백트래킹

 

1.  코드

 1 import sys
 2 
 3 while True:
 4    nums = list(map(int, sys.stdin.readline().split()))
 5    if nums[0] == 0:
 6       break
 7
 8    nums.pop(0)
 9    V = 6
10    stack = []
11
12
13    def dfs():
14        if len(stack) == V:
15            print(*stack)
16            return
17
18        if len(stack) == 0:
19            for i in nums:
20                stack.append(i)
21                dfs()
22                stack.pop()
23            return
24
25        for i in nums:
26            if i > stack[len(stack) - 1]:
27                stack.append(i)
28                dfs()
29                stack.pop()
30
31
32    dfs()
33    print()

(코드 링크)

 

2.  코드 설명

dfs >

주어진 숫자를 스택에 하나씩 집어넣는 함수를 작성하고

숫자가 스택에 쌓일 때마다 재귀 호출

(Line 21, Line 28)

 

재귀 호출의 탈출 >

스택에 데이터가 6개(로또 숫자)가 쌓이면

스택의 내용을 출력하고 탈출한다.

(Line 14)

 

백트래킹 조건 >

1. 숫자의 중복을 불허.

2. 숫자는 오름차순으로 출력.

-> 스택에 쌓기 전 예비 데이터가 스택의 top value 보다 클 경우에만 스택에 push 한다.

-> (예비 데이터가 조건에 충족하지 않을 경우 더 이상 탐색하지 않는다)

(Line 26)

 

재귀 호출 코드가 두 개로 나뉘어 있는 이유(Line 18~, Line 25~) >

비어있는 스택의 top value를 리스트 인덱스로 접근할 경우 IndexError 가 발생한다.

따라서 스택의 길이가 0 일 경우 조건 없이 스택에 넣고 재귀 호출한다.

(Line 18)

 

 

3.  참고

else 구문을 사용하지 않고 return 시키는 이유 >

코드 작성의 취향이라고 생각한다.

중첩된 조건문으로 분기 트리가 과도하게 늘어나면 가독성이 떨어지기 때문에

if 문 마지막에 return 으로 함수를 종료시키고

다시 시작 레벨부터 코드를 작성하는 방법을 선호한다.

guard clause라고 부른다.