[DFS/BFS/완전탐색] ▲ 6603번 - 로또 (완전 탐색)

[백준] 6603번 - 로또

풀이 시간: 10분 이내

 

(풀이1) combinations 라이브러리 사용

1) 문제 해결 아이디어

집합의 원소 k개 중에서 6개를 뽑는 경우의 수를 모두 출력하는 완전 탐색 문제이다.

전형적인 조합을 구하는 문제로 파이썬의 경우 combinations 라이브러리를 통해 쉽게 구현할 수 있다.

 

2) 소스코드

from itertools import combinations

while True:
  t = list(map(int, input().split()))
  k = t[0]  # 집합 원소 수
  # 종료 조건
  if(k == 0):
    break
  s = t[1 : len(t)]  # 집합
  for i in list(combinations(s, 6)):
    print(" ".join(map(str, i)))
  print()

 

<리스트를 문자열로 반환하기>

list1 = ['a', 'b', 'c']
''.join(list1)	# abc
' '.join(list1)	# a b c
'/'.join(list1)	# a/b/c

list2 = [0, 1, 2]
''.join(map(str, list2))	# 012
' '.join(map(str, list2))	# 0 1 2
'/'.join(map(str, list2))	# 0/1/2

'구분자'.join(리스트)	리스트의 문자들 사이에 구분자를 넣어 하나로 합쳐 문자열로 반환
'구분자'.join(map(str, 리스트))	리스트의 숫자들 사이에 구분자를 넣어 하나로 합쳐 문자열로 변환

문자로 된 리스트같은 경우에는 join()에 해당 리스트를 인자로 넘겨주면 바로 문자열로 변환이 되지만

숫자가 포함 된 리스트 같은 경우에는 일단 map(str, 리스트명)을 이용하여 문자로 바꾸어 준 값을 인자로 넘겨주어야 문자열로 변환이 된다.

 

[참고] https://blockdmask.tistory.com/468

[python] 파이썬 join 함수 정리 및 예제 (문자열 합치기)

[참고] https://codechacha.com/ko/python-convert-list-to-string/

Python - 리스트를 문자열로 변환

 

(풀이2) DFS(재귀) 이용

1) 문제 해결 아이디어

DFS로 풀 수 있는 문제였지만 코드를 짜기가 어려워서 다른 코드를 참고 했다.

다시 복습해야할 코드!

 

2) 소스코드

# 현재 깊이, 위치
def dfs(depth, idx):
  # 깊이가 6이 되면(종료 조건)
  if depth == 6:
    print(*res)
    return
    
  # 집합에서 탐색
  for i in range(idx, k):
    res.append(s[i])  # 집합 원소 삽입
    dfs(depth + 1, i + 1)
    res.pop()         # 맨 마지막 원소 빼기
    

while True:
  t = list(map(int, input().split()))
  k = t[0]  # 집합 원소 수
  # 종료 조건
  if(k == 0):
    break
  s = t[1 :]  # 집합
  res = []  # 결과를 담을 집합
  
  dfs(0, 0)
  print()

 

[참고] https://ji-gwang.tistory.com/267

백준 6603번 파이썬 문제풀이(브루트 포스 - 로또)