[백준/Python] 10971번: 외판원 순회 2

문제

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

10971번: 외판원 순회 2

---

문제 요약

외판원이 N개의 도시를 순회해야할 때, 필요한 최소 비용을 출력한다.

 

0번 ~ N -1번까지 도시들이 존재하고 (문제는 1번 ~ N번), 도시들 사이에는 길이 있다. (없을 수도 있다.)

 

외판원은 N개의 도시를 모두 거쳐야 하고 다시 원래의 도시로 돌아와야한다.

---

코드

# start번 도시에서 탐색 시작
# 현재 x번 도시에서 탐색 중
# 현재 경로로 순회 시 cost만큼 비용 발생
# depth개의 도시 순회 중
def find(start, x, cost, depth):
    global res

    if depth == N: 
    # N개의 도시를 모두 순회했다면
        if data[x][start]: 
        # x번 도시에서 start번 도시로 이동 가능한 경로가 존재한다면 (출발했던 도시로 다시 돌아갈 수 있다면)
            cost += data[x][start] # 돌아갈 때 발생한 비용 추가
            res = min(res, cost) # res값 갱신
        return

    for y in range(N): 
        if check[y] == 0 and data[x][y] != 0:
        # 아직 y번 도시를 지나지 않았고, x번 도시에서 y번 도시로 이동할 수 있는 경로가 존재한다면
            check[y] = 1 # 방문 표시
            find(start, y, cost + data[x][y], depth + 1)
            check[y] = 0 # 방문 표시 해제

N = int(input())

check = [0] * N # 몇번 도시를 거쳤는지 체크하는 배열

cost = 0 # 현재 비용

res = 10000000 # 최소 비용

depth = 1

# data[i][j]는 i번 도시에서 j번 도시로 갈 때 발생하는 비용
data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

# i번 도시에서 출발하는 것부터 탐색 시작
for i in range(N):
    check[i] = 1
    find(i, i, 0, 1) 
    check[i] = 0 # 체크 해제 필수!

print(res)

---

코드 설명

1. i번 도시에서 j번 도시로 갈 때 발생하는 비용을 data 배열에 저장한다.

 

2. 0번 도시에서 출발하는 것부터 N - 1번 도시에서 출발하는 것까지 탐색한다. (백 트래킹)

 

3. 총 비용 = N개의 도시를 모두 순회했을 시 발생한 cost + 자신이 출발한 도시로 돌아올 때 발생한 cost

 

4. 현재 탐색한 총 비용 cost와 이전까지 최소 비용 res를 비교하여 res값을 갱신한다.

 

5. 탐색이 종료되면, res값을 출력한다.