https://www.acmicpc.net/problem/10971
10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
https://github.com/stellaluminary/Baekjoon
GitHub - stellaluminary/Baekjoon
Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.
github.com
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)
어차피 순환된다면 한 번의 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)