10971번 - 외판원 순회 2

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

10971번: 외판원 순회 2

1년만에 풀어보는 TSP 문제였다... 

풀어본 문제임에도 오랜만에 푸니까 가물가물했다.. ㅜ

 

처음 작성했던 코드는 두 가지 오류가 존재했다. 

# 외판원 순회 2
import sys
input = sys.stdin.readline

N = int(input())
w = []
visited = [False for _ in range(N)]
answer = 1e7
for _ in range(N):
    w.append(list(map(int, input().split())))

def solve(cnt, start, cur, value):
    global answer
    if cnt == N:
        answer = min(answer, value+w[cur][start])
        return
    for i in range(N):
        if visited[i] == False:
            visited[i] = True
            solve(cnt+1, start, i, value+w[cur][i])
            visited[i] = False
            
solve(0, 0, 0, 0)
print(answer)

1. w[i][j]에서 i에서 j로 가는 경로가 없을 경우 2. 출발점으로 돌아가는 길이 없을 경우

즉, 경로가 없을 때를 고려하지 않아 해당 답안은 틀렸다. 

# 외판원 순회 2
import sys
input = sys.stdin.readline

N = int(input())
w = [list(map(int, input().split())) for _ in range(N)]
visited = [False for _ in range(N)]
answer = 1e7

def solve(cnt, start, cur, value):
    global answer
    if cnt == N-1:
        if w[cur][start] == 0: # 돌아갈 수 없음
            return
    if cnt == N:
        answer = min(answer, value+w[cur][start])
        return
    for i in range(N):
        if visited[i] == False and i != cur and w[cur][i] != 0:
            visited[i] = True
            solve(cnt+1, start, i, value+w[cur][i])
            visited[i] = False

solve(0, 0, 0, 0)
print(answer)

1번을 수정하기 위해 for 반복문 안에서 i != cur and w[cur][i] != 0이라는 조건을 추가하였다. 이동하고자 하는 노드가 현재 노드가 아니면서 다음 노드를 방문하지 않았고, 경로 또한 있을 때만 이동하는 것이다. 

2번을 수정하기 위해 cnt가 N-1일 때 출발점으로 돌아가는 경로가 있는지를 검사하여, 없으면 바로 return 하도록 했다.

 

이렇게 수정하니 통과할 수 있었다.

완전탐색과 백트래킹으로 해결할 수 있는 문제였다 :)