백트래킹

5209. [파이썬 S/W 문제해결 구현] 5일차 - 최소 생산 비용

하루를 끙끙대며 문제를 풀다가 때려치고 테트리스 구현하다가 막혀서 다시 돌아와서 문제를 풀었다. 그렇게 어려운 문제는 아니었는데 아무래도 백트래킹 문제가 워낙 어렵다 보니 끙끙댔나보다.

각설하고, 깃허브에는 올리지만 추후에 내가 백트래킹 문제를 풀면서 이걸 내가 어떻게 풀었었지 라고 할까봐 자세한 설명과 함께 솔루션을 쓰겠다.

사실 내가 처음부터 이렇게 풀진 않았고, 답지를 보듯 다른 분 풀이를 보고 내가 나름대로 해석해 내서 풀어봤다.

1. 백트래킹 문제이므로 위->아래 순으로 재귀 함수
2. 재귀 함수 고려할 것:
   (1) 다음 재귀 때 변수값 어떻게 되는 지
   (2) 종료 조건(leaf node)(FIXED1): 이때 시간 복잡도(O함수)도 고려
3. 재귀 함수에 for문이 들어가게 되면:
   다음 for문에서 변수들이 어떤 값을 가지는 지 확인하기(FIXED2)
4. 필요한 변수 및 리스트
   • inp_list: 각 공장별 생산비용
   • min:
   • sum:

INF = 10000000
min = INF


def minCost(dep, sum):
    global min
    # 종료조건 1: prunning
    if sum > min:
        return
    # 종료조건 2: 깊이가 트리의 높이만큼일 때: 최대한 종료를 빨리 할 수 있으면 좋음.
    # FIXED: return문을 dep == len(inp_list) 바로 밑에 위치하니까 런타임 에러 해결, 리프 노드에서 for문 도는 게 생각보다 큰 시간을 소요하나 봄
    if dep == len(inp_list):
        if min > sum:
            min = sum
        return

    for j in range(len(inp_list[dep])):
        if visited[j] == False:
            # 자식 노드 중 미방문 노드만 방문하기
            visited[j] = True

            # 재귀 호출: FIXED: sum += inp_list[dep][j]는 오류 코드, 그러면 다음 for문에서도 sum이 이대로 반영됨
            minCost(dep+1, sum + inp_list[dep][j])

            # **다시 돌아왔을 때 다른 자식 노드 방문 가능하게 하는 밑작업(for문: 이미 방문한 자식 노드는 제외하고 다른 노드 방문하려고 함)**
            visited[j] = False


T = int(input())
for t in range(T):
    n = int(input())
    inp_list = []
    for _ in range(n):
        inp_list.append([int(i) for i in input().split()])
    visited = [False]*n
    min = INF
    minCost(0, 0)
    print("#%d %d" % (t+1, min))