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

📌 문제 링크

외판원 순회 2

📌 문제를 풀기전 생각 정리

여러 상황을 고민해 문제를 풀 때 도움이 될 만한 것을 적어 놓고 소스코드를 작성했지만 시간 복잡도가 3340ms가 나와버렸다.

📌 코드

// 3340ms
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
load_map = [list(map(int, input().split())) for _ in range(N)]
next_position_dic = defaultdict(list)

for i in range(N):
    for j in range(N):
        if load_map[i][j] != 0:
            next_position_dic[i].append(j)

result_min_value = []
load_min_value = []
def dfs():
    pop_position = stack.pop()

    if len(visited) == N + 1:
        result_min_value.append(sum(load_min_value))
        return

    for next_position in next_position_dic[pop_position]:
        # 이전에 방문한 기록이 없거나
        # 방문한 기록이 있어도 마지막 포지션에서 첫번째 포지션으로 가는 길은 check 해야하므로(마지막 포지션에서 첫번째 포지션으로 가는길이 있을 때만)
        if next_position not in visited or (len(visited) == N and next_position == visited[0] and visited[0] in next_position_dic[visited[-1]]):
            visited.append(next_position)
            stack.append(next_position)
            load_min_value.append(load_map[pop_position][next_position])
            dfs()
            visited.pop()
            load_min_value.pop()


visited = []
stack = []
for key in list(next_position_dic.keys()):
    visited.append(key)
    stack.append(key)
    dfs()
    visited.pop()

print(min(result_min_value))

📌 해설 참조 후 생각 정리

1. visited를 통해 방문 check, stack을 통해 이동했던 내역을 저장
2. 지금 구한 값들의 최소값보다 현재 진행되고 있는 값 + 진행 횟수 * board의 최소값이 크다면 retrun
   => 최소값이 아닐수도 있지만 최소값을 넣어주었는데도 불구하고 구한 값이 크다면 가망이 없으므로 가지치기
3. 이전의 필요없는 소스코드 제거 및 최소값을 통한 가지치기
   => 특정 도시에 대응하는 도시 저장(defaultdict)
   => dfs 안쪽이랑 바깥쪽에 중복되는 소스코드

📌 해설 참조 코드

// 335ms
import sys
input = sys.stdin.readline

N = int(input())
load_map = [list(map(int, input().split())) for _ in range(N)]

def dfs():
    if result_min_value and stack and (N + 1 - len(stack)) * min_value + stack[-1][1] >= min(result_min_value):
        return

    if len(stack) == N:
        first_position = stack[0][0]
        final_position = stack[-1][0]
        if load_map[final_position][first_position] != 0:
            final_value = stack[-1][1]
            value = final_value + load_map[final_position][first_position]
            result_min_value.append(value)
        return

    for idx in range(N):
        if not visited[idx]:
            # 한 곳도 방문하지 않았을 경우
            if not stack:
                stack.append([idx, 0])
            else:
                prev_position = stack[-1][0]
                if load_map[prev_position][idx] == 0:
                    continue
                else:
                    prev_value = stack[-1][1]
                    value = prev_value + load_map[prev_position][idx]
                    stack.append([idx, value])
            visited[idx] = True
            dfs()
            stack.pop()
            visited[idx] = False

visited = [False] * N
stack = []
min_value = 1000000
for i in range(N):
    for j in range(N):
        if load_map[i][j] != 0: min_value = min(load_map[i][j], min_value)
result_min_value = []

dfs()

print(min(result_min_value))

📌 문제 풀어본 후기