[백준] 로또(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제

단순히 combination을 구하는 것 같은 아주 간단한 문제이지만, 사실 dfs로 풀어야 진가를 볼 수 있는 문제이기도 했다! 

 

# 입출력

K가 집합 S에 포함되는 수의 개수인데 생각보다 6에서 13 사이이면 작은 범위라고 생각했다. 그래서 처음으로 itertools 모듈을 고려하게 된 것 같다. 

 

# Idea

처음에는 앞서 언급한대로 from itertools import combinations 을 사용했다. 범위가 작게 주어졌다고 생각했기 때문이다. 이런 방식으로 구한 답도 맞았지만, 이 문제는 백트래킹 단원의 문제인 만큼 dfs로 접근하는 것이 중요한 문제였던 것 같다. 사실 이제 dfs는 좀 익숙한 상태였는데, 모두 2차원 그래프를 대상으로 한 dfs 문제를 풀이했었다. 그래서 이 문제는 익숙치 않았던 것 같다. 

보통 조합(Combination)을 찾는 문제는 1차원 DFS로 구현할 수 있다고 생각한다고 한다. 이러한 motivation은 다음과 같다. 

그림에 대한 설명을 하자면 우선 기본적인 깊이 우선 탐색(DFS)의 방식은 유지하며, unvisited 노드를 중심으로 깊게 탐색을 한다. (그림에서는 주황색으로 unvisited를 표시하였다) 그런데 1차원 DFS이기 때문에, 노드를 우선 1차원 리스트 (단순 python 리스트)에 적재하고 이들을 단순 for문으로 순회하며 dfs 재귀함수를 적용한다. 

보통 2차원 그래프 기반 dfs는 다음과 같이 구성되는게 일반적이다. 애초에 graph input이 2차원 리스트로 주어진다. 

def dfs(graph, v, visited):

  visited[v] = True     # 현재 노드 방문처리
  print(v, end=' ')     # 스택에 넣는 순서 (순회하는 순서)로 출력

  # 현재 노드와 연결된 다른노드 재귀적 방문
  for i in graph[v]:
    # 방문 기록이 없으면 ?
    if not visited[i]:
      dfs(graph, i, visited)     # 여기서부터 다시 dfs 재귀호출

하지만 이 로또 문제와 같은 1차원 그래프 기반의 dfs를 이용하는 문제는 다음과 같이 dfs 함수가 구성된다. 

def dfs(graph, s, visited):    # s는 로또 집합 리스트 / lotto에 조합 내 원소 적재 

  t_visited = visited[:]

  ## visited 노드 순회 반복문 (i는 0부터 k-1까지 )
  for i in range(len(t_visited)):
    
    # unvisited 노드 중심 반복문 
    if not t_visited[i]:               # 방문하지 않았으면 
      t_visited[i] = True
      dfs(graph + [i], s, t_visited)   # lotto에 계속 unvisited index 적재

애초에 graph가 1차원 리스트로 주어지기 때문에, 마지막 줄에서 graph + [i] 식으로 노드를 적재해주는 식으로 dfs가 진행된다는 차이점이 있다. 

 

# Code

def dfs(lotto, s, visited):    # s는 로또 집합 리스트 / lotto에 조합 내 원소 적재 
  # len이 6이면 print 
  if len(lotto) == 6 : 
    for i in range(6):
      print(s[lotto[i]], end=' ')   # S에서 lotto[i]에 해당하는 인덱스 출력 
    print()
    return 

  t_visited = visited[:]

  ## visited 노드 순회 반복문 (i는 0부터 k-1까지 )
  for i in range(len(t_visited)):
    if not t_visited[i]:               # 방문하지 않았으면 
      t_visited[i] = True
      dfs(lotto + [i], s, t_visited)   # lotto에 계속 unvisited index 적재 
     
while True : 
  s = list(map(int, input().split()))   # lotto 집합 S를 입력 
  if s[0] == 0 :      # 종료조건 
    break

  s.pop(0)   # 첫 k 원소 제외 
  visited = [False] * len(s)

  dfs([], s, visited)   # 빈 리스트에서 시작 
  print()

참고로 lotto + [i] 이 과정이 이해가 잘 안되어서, 출력해본 결과는 다음과 같았다. 특히 lotto 리스트에 집합 원소의 index를 적재하는 시스템이라는 점은 유의해야한다!