[Python/Baekjoon] 10971. 외판원 순회 2

💬 문제

문제 난이도: 백준 실버 2

문제 링크: https://www.acmicpc.net/problem/10971

❗️접근 방법

1. 재귀를 사용한다.
   1) 이미 방문한 노드인지 점검한다.
   2) 방문하지 않은 노드라면 현재 노드에서 갈 수 있는 노드인지 체크한다.
   3) 위의 2개의 조건을 통과하면 재귀함수를 호출한다.
2. 백트래킹
   1) 재귀함수를 호출하기 전에 해당 노드를 방문하겠다는 체크를 하고
   2) 호출한 재귀함수가 종료되면
   3) 1)에서 표시한 노드(제일 최근에 추가된 노드)에 대한 방문 체크를 지워준다.

✅ 내 코드 1

import sys
N = int(input())
min_value = 1000000* (N)
travel = []
for _ in range(N):
    travel.append(list(map(int,input().split(' '))))

def dfs(startNode, nextNode, value, visited):
    global min_value

	# 다 순회하지 않아도 min_value를 초과하면 다 순회할 필요가 없다.
    if value + travel[nextNode][startNode] > min_value:
        return False

	# 모든 노드를 순회한 경우
    if len(visited) == N:
    	# 마지막 노드에서 제일 처음으로 방문한 노드로 오는 방법이 있는지
        if travel[nextNode][startNode] != 0:
            min_value = value + travel[nextNode][startNode]
            return True
        return False

    for i in range(N):
        # 갈 수 있는 노드인지 + 이미 방문한 노드는 아닌지
        if travel[nextNode][i] != 0 and i not in visited:
            visited.append(i)
            dfs(startNode, i, value+travel[nextNode][i], visited)
            visited.pop()

# i는 시작하는 node
# [i]를 하는 이유는 마지막으로 돌아올 노드를 넣어줌
# 기본적으로 backtracking
result = 0
for i in range(N):
    dfs(i, i, 0, [i])
        
print(min_value)

✅ 내 코드 2

import sys
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
routes = []
for _ in range(N):
    routes.append(list(map(int, input().split(' '))))

visited = [0 for _ in range(N)]

minWeight = 1000000 * N

# preIdx: 바로 전에 방문 노드의 인덱스
# startNode: 맨 마지막에 돌아올 처음 노드 인덱스
def solution(depth, total, preIdx, startNode):
    global minWeight

    if depth == N:
    	# 마지막 노드에서 처음에 시작한 노드로 갈 수 있는지
        if routes[preIdx][startNode] != 0:
            total += routes[preIdx][startNode]
            minWeight = min(minWeight, total)
        return
    else:
        if total > minWeight:
            return

        for i in range(N):
            # 이미 방문한 노드인지 + 다음으로 방문할 수 있는 노드인지
            if visited[i] == 0 and routes[preIdx][i] != 0:
                # 방문 체크 on
                visited[i] = 1
                solution(depth+1, total+routes[preIdx][i], i, startNode)
                #방문 체크 off
                visited[i] = 0


# depth가 0일 때
for i in range(N):  
    visited[i] = 1
    # 1인 이유: 시작하는 노드를 넣어주고 시작하므로
    solution(1, 0, i, i)
    visited[i] = 0

print('{}'.format(minWeight))