문제 : https://www.acmicpc.net/problem/10971
목표 :
- 외판원이 가장 적은 비용으로 모든 도시 도는 것
조건 :
- 도시의 수는 2 <= N <= 10
- 한번 간 도시는 돌아오는 것이 아닌한 가지 않는다.
- 0으로 된 곳은 갈 수 없는 곳이다.
푸는법 :
- dfs
- permutation으로 완전 탐색을 하는 것이다.
dfs로 푸는 법
- 사실 왜 답인지 모르겠다 (…)
- 왜 cnt가 n인 것은 3번 밖에 안되는지…. 의문 ㅜㅜ
- 이거 아시는 분 덧글 좀 주세요
- 참고자료 :https://blockdmask.tistory.com/229
import sys
sys.setrecursionlimit(10**6)
n = int(input())
arr = [list(map(int,input().split()))for _ in range(n)]
ret = sys.maxsize
visited=[-1]*n
def dfs(start, x, res, cnt):
global ret
if cnt == n and start == x : # 다 돌았고, 다시 돌아왔음
ret = min(ret, res) # 총 값중에서 ret이랑 비교 -> dfs는 각 위치마다 시작한다
for y in range(n):
if (visited[y] != -1 or arr[x][y] == 0) : continue
visited[y] = 1
res += arr[x][y]
if res <= ret:
dfs(start, y, res, cnt+1)
visited[y] = -1 # visited 다 초기화
res -= arr[x][y] # res도 초기화
for i in range(n):
dfs(i, i, 0, 0)
print(ret)
permutation
- 일단 brute force로 다 해보는 것이다
- if i[0] != 0: break는
- 자바나 cpp은 이거 없어도 되는데 파이선은 안된다.
- 근데 왜 되는 걸까?
- (1, 0, 2, 3) 과 (0, 1, 3, 2)이 같기 때문일 것 같다.
- 맞는 생각일까… 어차피 0을 시작점으로 모든 경우의 수 다 해봤으니 되는 것 같다.
from itertools import permutations
import sys
N = int(input())
NPerm = [*permutations(list(range(N)))]
W = [list(map(int, input().split())) for _ in range(N)]
ans = sys.maxsize
for i in NPerm: #permutation을 돌린다.
sums = 0 # 일단 sums에 값을 차곡차곡
ok = True
for j in range(N-1):
cost = W[i[j]][i[j+1]] # permutation에서 정한 값들을 돈다.
if cost == 0: # cost가 0이나오면 그길로는 못간다.
ok = False
else: sums += cost
if ok and W[i[N-1]][i[0]] != 0:
# W[i[N-1]][i[0]] != 0 이건 돌아오는 길이 존재하는 것 확인하는 것
sums += W[i[N-1]][i[0]]
ans = min(ans, sums)
if i[0] != 0: break
print(ans)