[백준]10971- 외판원 순회 2 문제 풀이(파이썬,Python)

문제

10971번: 외판원 순회 2

들어가며

문제의 중요한 점을 뽑자면 다음과 같다

1. 1번부터 N번까지 N개의 도시가 있음.
2. 특정 도시에서 다른 도시로 이동하는 비용이 2차원 배열로 주어짐.
3. 모든 도시를 한 번씩 방문한 후, 다시 출발 도시로 돌아오는 경로 중 최소 비용을 구해야 함.
4. 어떤 도시 A에서 도시 B로 갈 수 없는 경우 비용이 0으로 표시됨.

 

➡ 출발 도시는 정해져 있지 않고, 어떤 도시에서든 출발할 수 있음.
➡ 비용 행렬이 주어지며, 이 행렬은 대칭이 아닐 수도 있음(즉, cost[A][B] ≠ cost[B][A]).

 

돌아오는 경로 중에 계산해야 하므로 백트래킹으로 접근할 수 있다.

코드

n = int(input())
arr = []
visited = [False] * n
result =  1000000000

for i in range(n):
    costs = list(map(int, input().split()))
    arr.append(costs)

def search(start, cost, visited_count):
    global result
    if visited_count == n:
        if arr[start][0] != 0 :
            cost += arr[start][0]
            result = min(result, cost)
        return
    if cost >= result:
        return

    for i in range(n):
        goal_cost = arr[start][i]
        if goal_cost != 0 and not visited[i]:
            visited[i] = True
            search(i, cost + goal_cost, visited_count + 1)
            visited[i] = False

visited[0] = True
search(0,0,1)
print(result)

풀이

n = int(input())
arr = []
visited = [False] * n
result =  1000000000

for i in range(n):
    costs = list(map(int, input().split()))
    arr.append(costs)

 

백트래킹을 진행하기 전에 셋팅을 진행한다.

arr은 문제에서 주어지는 2차원 배열을 의미한다.

visited는 방문 여부를 확인하는 1차원 배열이다. 도시의 개수만큼 존재해야 한다.

result는 최소 비용을 구하기 위한 임의의 큰 값이다.

 

def search(start, cost, visited_count):
    global result
    if visited_count == n:
        if arr[start][0] != 0 :
            cost += arr[start][0]
            result = min(result, cost)
        return
    if cost >= result:
        return

    for i in range(n):
        goal_cost = arr[start][i]
        if goal_cost != 0 and not visited[i]:
            visited[i] = True
            search(i, cost + goal_cost, visited_count + 1)
            visited[i] = False

대망의 재귀문이다.

파라미터의 start는 현재 탐색을 위해 도착한 도시의 인덱스 값이다. 2차원 배열 arr 에서 행을 의미한다.

cost는 도시를 탐색하면서 이때까지 쌓인 비용의 값이다.

visited_count는 탐색한 도시의 갯수이다.

 

return을 하는 두 Base Condition은 일단 후에 설명하겠다.

for i in range(n):
    goal_cost = arr[start][i]
    if goal_cost != 0 and not visited[i]:
        visited[i] = True
        search(i, cost + goal_cost, visited_count + 1)
        visited[i] = False

 

반복문을 보게 되면, 모든 도시를 다 체크한다.

goal_cost는 다음 목적지인 arr[start][i]까지 도달하는데 필요한 비용이다.

다음 도시까지의 goal_cost가 0이 아니고, 다음 도시를 방문한 적이 없다면 이를 방문 처리(visited[i] = True)를 하고 다음 재귀문으로 넘어간다.

백트래킹으로 다시 돌아왔을 땐, 방문을 해제한다.

 

if visited_count == n:
    if arr[start][0] != 0 :
        cost += arr[start][0]
        result = min(result, cost)
    return
if cost >= result:
    return

Base Condition을 보면 위와 같다.

만약 방문한 도시의 개수가 n이고 출발지로 돌아갈 수 있다면(0이 아니라면) 그 비용을 더하고 최종적으로 결과값에 넣게 된다.

여기서 0이 출발지가 되는 이유는 search 함수 호출 부분에서 후술할 것이다.

 

다음 조건문을 보면 이때까지 쌓은 비용이 만약 제일 최근한 계산한 result보다 크면 탐색을 종료하는 구문이다. 최적화를 위해 넣어두었다.

 

visited[0] = True
search(0,0,1)
print(result)

함수 호출 부분이다.

0번 도시에서 출발하는 것으로 가정했기 때문에, visited[0] 은 True고 visited_count를 1로 설정하고 함수를 시작한다.