[백준][10971] 외판원순회2

• 문제
  • 10971번: 외판원 순회 2
• 해설

  • import sys
    
    N = int(sys.stdin.readline())
    matrix = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    base_idx = [x for x in range(N)]
    
    
    def next_permutation(list):
        last_asc_idx = 0
        for i in range(len(list) - 1):
            if list[i] < list[i + 1]:
                last_asc_idx = i
    
        val_at_last_asc_idx = list[last_asc_idx]
        last_idx_larger_than_val_at_last_asc_idx = 0
        for j in range(last_asc_idx + 1, len(list), 1):
            if val_at_last_asc_idx < list[j]:
                last_idx_larger_than_val_at_last_asc_idx = j
    
        if last_asc_idx == 0 and last_idx_larger_than_val_at_last_asc_idx == 0:
            return False
        else:
            list[last_asc_idx], list[last_idx_larger_than_val_at_last_asc_idx] = \
                list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx]
            last_idx_larger_than_val_at_last_asc_idx = len(list) - 1
            while (last_asc_idx + 1 < last_idx_larger_than_val_at_last_asc_idx):
                list[last_asc_idx + 1], list[last_idx_larger_than_val_at_last_asc_idx] = \
                    list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx + 1]
                last_asc_idx += 1;
                last_idx_larger_than_val_at_last_asc_idx -= 1
            return True
    
    
    def factorial(k):
        if k == 0 or k == 1:
            return 1
        else:
            res = k
            for i in range(1, k, 1):
                res *= i
            return res
    
    
    total_available_count = factorial(N - 1)
    
    res = []
    for j in range(total_available_count):
        cost = 0
        out_inner_loop = False
    
        # 마지막 도시에서 처음 도시로 가지 못하는 경우 발견
        if matrix[base_idx[N - 1]][base_idx[0]] == 0:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
        else:
            cost += matrix[base_idx[N - 1]][base_idx[0]]
    
        for i in range(N - 1):
            # 이동이 불가능한 도시의 경우
            if matrix[base_idx[i]][base_idx[i + 1]] == 0:
                out_inner_loop = True
                break
            else:
                cost += matrix[base_idx[i]][base_idx[i + 1]]
        if out_inner_loop:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
    
        # 가능한 경우가 처음 나왔을 때
        if len(res) == 0:
            res.append(cost)
    
        # 가능한 경우를 이전과 비교  
        else:
            if cost < res[0]:
                res[0] = cost
    
        # 다음 이동 경로 체크
        next_permutation(base_idx)
    
    print(res[0])

• 포인트
  • BruteForce임을 알아채야한다.
  • next permutation을 구현할 수 있어야한다.