[Baekjoon] 10971번 : 외판원 순회 2 (Python, 백트래킹)

[Baekjoon] 10971번 : 외판원 순회 2 (Python, 백트래킹)

 

목차

 

 

 

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 메모리 119184KB / 시간 1188ms / 코드 길이 533B (PyPy3)

 

dfs 내부 종료 조건으로 l[start][init] != 0이 없으면 틀림. (주의)

 

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
t = []
visit = [0] * n
m = 1e9

def dfs(depth, start, init):
    global m
    if depth == n and l[start][init] != 0:
        m = min(m, sum(t)+l[start][init])
        return
    for i in range(n):
        if not visit[i] and l[start][i] != 0:
            visit[i] = 1
            t.append(l[start][i])
            dfs(depth+1, i, init)
            t.pop()
            visit[i] = 0

for i in range(n):
    visit[i] = 1
    dfs(1, i, i)
    visit[i] = 0
print(m)

 

방법 2 - 메모리 30840KB / 시간 792ms / 코드 길이 433B

 

어차피 순환된다면 한 번의 dfs만 돌려도 된다는 사실을 깨달음

별도의 list를 활용한 값 저장보다 저장한 값으로 재귀하는 함수를 활용하는 것이 편하다는 사실을 깨달음

 

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]
visit = [0] * n
m = 1e9

def dfs(depth, start, cost):
    global m
    if depth == n-1 and l[start][0] != 0:
        m = min(m, cost+l[start][0])
        return
    for i in range(n):
        if not visit[i] and l[start][i] != 0:
            visit[i] = 1
            dfs(depth+1, i, cost+l[start][i])
            visit[i] = 0
visit[0] = 1
dfs(0, 0, 0)
print(m)