이 문제는 오랜시간동안 봤는데도 좀 이해가 덜 되는 문제이다.
코드 1번이 좀 더 이해가 잘 되는거 같아서 1번으로 설명을 해보겠다. min_value를 출력할 최솟값으로 정의를 해준다.
dfs 함수에서는 도시의 개수만큼 for문을 돌려서 갈수 있는 길(0이 아닐경우)이면서 방문을 안했고 이때까지 계산한 최소값보다 value가 적으면 visited에 그 도시를 추가해준다. 다시 dfs를 해주고 visited.pop을 해준다.(이때 pop을 왜 하는지 모르겠다)
그리고 마지막 도시에서 출발도시로 가는 비용이 0이 아닐경우(즉 갈수 있다면) minvalue와 이번에 구한 값과 비교 했을때 더 적은 애를 minvalue에 넣는다.
그 다음 main에서는 출발점을 0,1,2,3 이렇게 4번해서 다 돌아준다.
dfs(i, i, 0, [i])으로 해주고 min_value를 출력해준다.
import sys
N = int(input())
travel_cost = [list(map(int, input().split())) for _ in range(N)]
min_value = sys.maxsize
def dfs(start, next, value, visited):
global min_value
if len(visited) == N:
if travel_cost[next][start] != 0:
min_value = min(min_value, value + travel_cost[next][start])
return
for i in range(N):
if travel_cost[next][i] != 0 and i not in visited and value < min_value:
visited.append(i)
dfs(start, i, value + travel_cost[next][i], visited)
visited.pop() #왱??
for i in range(N):
dfs(i, i, 0, [i])
print(min_value)
N= int(input())
maps=[]
for _ in range(N):
maps.append(list(map(int,input().split())))
visited= [0]*N
tmp=1000000
add=0
def dfs(i,add,visited):
global tmp
if add> tmp:
return
if sum(visited)==N-1:
if maps[i][0]:
tmp=min(tmp,add+maps[i][0])
return
for j in range(1,N):
if maps[i][j] and visited[j]==0:
visited[j]=1
dfs(j,add+maps[i][j],visited)
visited[j]=0
for i in range(1,N):
if maps[0][i]:
visited[i]=1
dfs(i,add+maps[0][i],visited)
visited[i]=0 #why???
print(tmp)