Python_수업 (9)

오늘 할일

DFS 심화

• intro : 외판원 순회 문제
• DFS(재귀)를 통한 순열 직접 구현
• 백트래킹(가지치기)
• 준비물 : DFS(재귀) 코드

---

복습!

1. 그래프 이론 DFS(깊이 우선 탐색 → 스택, 재귀 / 경로) / BFS(너비 우선 탐색 → 큐 / 최단거리) : 세팅 → 방문 → 탐색

DFS 심화

• intro : 외판원 순회 문제
  • N 개의 도시를 순회하는 가장 빠른 경로 → N 개의 도시 줄 세우기! → DFS(깊이 우선 탐색)
  • 가능한 모든 경로(경우의 수) 확인하기! → 가능한 모든 DFS 반복하기!
• DFS(재귀)를 통한 순열 직접 구현
  • 순열과 조합 (itertools)
    • permutation(순열) : N개 중에 N개를 뽑아 줄을 세운다.
      • 재귀순열

      # 기본적인 틀
      def perm(depth):
          # 종료 조건
          if depth == M:
              print(ans)
              return
          
          # 탐색(for 반복)
          for i in range(N):
              if not check[i]: # 방문 X
                  check[i] = 1 # 방문 체크
                  sel[depth] = arr[i] # 정답추가
                  perm(depth+1)   # 다음 depth
                  check[i] = 0    # 방문 해제
      

      arr = ['A', 'B', 'C']  # 재료 리스트
      sel = [0, 0, 0]  # 인형뽑기 selection
      check = [0, 0, 0]  # 뽑을지 말지 결정하는 리스트
      
      def perm(depth):  # 각자 뎁스에서는? 
      		# 방문 & 종료조건
          if depth == 3:  # 최고 뎁스에 도달했으면? # if depth == len(sel)
              print(sel)  # print
              return
      		
      		# 탐색
          for i in range(3):  # 3번의 화살표 떨어트릴 기회
              if not check[i]:  # 각 기회 안에서 check를 보고 멈출 수 있는지 보고?
                  check[i] = 1  # 멈출 수 있다면 if 통과했으니까 자리 차지했다고 표시하고
                  sel[depth] = arr[i]  # 화살표가 떨어진 위치의 재료리스트
                  perm(depth+1)
                  check[i] = 0  # 돌아나오면서 다시 다음을 위해 초기화!! (중요)
      
      perm(0)
      

• 백트래킹(가지치기)
  • 유망하지 않은(정답이 될 가능성이 더이상 없는) 가지 탐색 중단
  • 문제 의식 : DFS 순열의 시간복잡도 O(N!) → 굳이 모든 경우의 수를 다 확인해봐야 하나..?
• 준비물 : DFS(재귀) 코드