10971번: 외판원 순회 2
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
dfs와 백트래킹을 이용하여 풀었는데 왜 틀리다고 나올까.. 삽질하다가 마지막에 시작했던 노드로 다시 돌아오는 부분을 검사할 때 cnt==3이라고 조건을 달아둔 걸 발견했다. 당연히 N-1이라고 해야 하는 것을ㅠㅠ
import sys
N = int(sys.stdin.readline())
W = []
for _ in range(N):
W.append(list(map(int, sys.stdin.readline().split())))
check = [False]*N
ans = 10**9
tmp = 0
cnt = 0
def dfs(i, start):
global tmp, cnt, ans
check[i] = True
if (cnt==N-1):
if (W[i][start]!=0):
ans = min(ans, tmp+W[i][start])
return
for n in range(N):
if (check[n] == False and W[i][n]!=0):
tmp+=W[i][n]
cnt+=1
dfs(n, start)
check[n] = False
tmp-=W[i][n]
cnt-=1
return
for i in range(N):
dfs(i,i)
check = [False]*N
cnt = 0
tmp = 0
print(ans)
pypy3 통과
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 14496번: 그대, 그머가 되어 (0) | 2021.05.25 |
---|---|
BOJ 18352번: 특정 거리의 도시 찾기 (0) | 2021.05.25 |
BOJ 19621번: 회의실 배정2 (0) | 2021.05.12 |
BOJ 1987번: 알파벳 (0) | 2021.02.08 |
BOJ 2606번: 바이러스 (0) | 2021.02.08 |