백준 10971 : 외판원 순회2 (Python)

본문 링크

def BackTracking(deep, total, index, start):
    global Answer


    if deep == N and start == index:
        Answer = min(Answer, total)
    if total > Answer:
        return
    for i in range(N):
        if not visit[i] and graph[index][i]!=0: # 가중치가 0 인 곳은 길이없는곳이다.
            visit[i] = True
            BackTracking(deep + 1, total + graph[index][i], i, start)
            visit[i] = False


N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
Answer = int(1e9)

for i in range(N):
    visit = [False] * N
    BackTracking(0, 0, i, i)

print(Answer)

📌 어떻게 접근할 것인가?

백트래킹을 사용해서 모든 경로를 탐색했습니다
visit 배열은 더 효율적으로 탐색하기 위해서 1차원 배열로 사용하였습니다.

문제에서 외판원 순회는 , 시작지점에서 출발하여 똑같은 지점을 방문하지 않고 단 한번씩만 방문해서 마지막 도착지점이 시작지점과 동일한지 판별하는 문제입니다.

if deep == N and start == index:
	Answer = min(Answer, total)

이는 위와 같이 판별했습니다.

방문한 횟수와 도시의 개수가 같고 , 시작지점과 도착지점이 같은지 확인합니다.

만약 참이라면 최소값을 갱신해줍니다.

if total > Answer:
	return

이때 중요한 것은 지금까지 이동한 경로의 합이 최소값보다 크다면 함수를 바로 종료해야합니다.
즉 무의미한 순회를 제거해야지 모든경로를 탐색할때 더 효율적으로 탐색가능합니다.

for i in range(N):
	if not visit[i] and graph[index][i]!=0: # 가중치가 0 인 곳은 길이없는곳이다.
		visit[i] = True
		BackTracking(deep + 1, total + graph[index][i], i, start)
		visit[i] = False

이후 총 $N$ 번 동안 재귀를 수행합니다.
방문하지 않은 지점이고 그래프의 값이 0 이 아닌 지점에 대해 탐색합니다.
깊이를 1 증가시키고 total 변수의 값을 그래프의 값만큼 증가시킵니다.
또한 3번째 매개변수에 i 를 넣은 이유는 행의 인덱스를 갱신하기 위해서 입니다.
start 는 가장 처음 출발한 시작점을 의미합니다.

중요한 것은 행과 열의 인덱스가 다를때 꼭 0 이 아니라는 보장이 없습니다.

• 4
  0 10 15 20
  5 0 9 0
  6 13 0 12
  8 8 9 0

위와 같은 예제에서 $(2,4)$ 의 값은 0 입니다.
답은 39 입니다. 즉 0 이라고 가중치가 0 이라 생각해서 이동하면 안됩니다.

for i in range(N):
    visit = [False] * N
    BackTracking(0, 0, i, i)

도시가 $N$ 개 있을때 모든 도시에 대해서 출발을 해야하기 때문에 백트래킹을 총 $N$ 번 실행했습니다.

또한 매번 백트래킹이 끝날때마다 visit 방문처리배열을 초기화 해줍니다.