[Advanced] 2. 완전 검색 - 문제편 (삼성 sw expert 5188 5189)

*SW Expert Academy - Advanced Course를 공부한 내용입니다.

이론편 : 2021.07.20 - [Coding Test/SW expert (삼성)] - [Advanced] 2. 완전 검색 - 이론편

[Advanced] 2. 완전 검색 - 이론편

---

# 5188. 최소합

NxN 크기의 판에서 오른쪽 또는 아래로만 이동할 수 있다고 할 때, 왼쪽 위부터 시작하여 오른쪽 아래까지 이동하는 최소합을 구하라.

• 완전 검색 방법을 이용, 재귀함수를 정의하여 전체 경로의 합을 구하고, 그 중 최소값을 선택하는 풀이법
  • 1개의 테스트케이스가 런타임 에러로 실패
    

            N = int(input())
            board = []
            for i in range(N):
                board.append(list(map(int, input().split())))
    
            summ_list = []
            def TSP(summ, row, col):
                summ += board[row][col]
                if row < N-1:
                    TSP(summ, row+1, col)
                if col < N-1:
                    TSP(summ ,row, col+1)
                if (row==N-1) and (col==N-1):
                    summ_list.append(summ)
                    return
    
            TSP(0, 0, 0)
            print(f'#{test_case} {min(summ_list)}')

• N이 13을 넘어가면 경우의 수가 엄청 많아지는데 리스트에서 min()연산의 시간 복잡도가 O(n)이라서 런타임 에러가 난 듯 함
  • TSP 함수안에 아래와 같은 조건문을 넣음. 현재 더하고 있는 summ이 추가된 summ_list의 최솟값보다 작으면 더 진행할 필요없이 리턴하는 조건문
  • 하지만, 마지막 경우의 수가 가장 최소값인 경우에는 결국 런타임 에러날 듯..? 
    

                if len(summ_list) >0 and summ > min(summ_list):
                    return​

 

# 5189. 전자카트

1번에서 시작하여 N개의 구역을 들렸다가 다시 1로 돌아오는 문제.
각각의 구역에서 다른 구역으로 이동하는 비용이 주어짐. 양방향의 비용이 같지 않음.(오르막, 내리막이 다르니까!)
* 단순 외판원 문제라기엔 1로 돌아와야하는게 달랐음

• 완전 검색으로 문제 풀기
  

          N = int(input())
          e = [list(map(int, input().split())) for i in range(N)]
  
          stamps =[i for i in range(1,N)]
          stamp_case = list(itertools.permutations(stamps))
          min_sum = 100*N
          for j in range(len(stamp_case)):
              case = stamp_case[j]
              foot = 0
              sum = 0
              for stamp in case:
                  if sum > min_sum:
                      break
                  sum += e[foot][stamp]
                  foot = stamp
              sum += e[foot][0]
              if sum < min_sum:
                  min_sum = sum
  
          print(f'#{test_case} {min_sum}')​