백준 10971번 외판원 순회 파이썬

백준 10971번 외판원 순회 (백트래킹)

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

무엇?

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고,
도시들 사이에는 길이 있다. (길이 없을 수도 있다)
한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 경로를 구하려고 함
단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외)
가장 적은 비용을 들이는 여행 계획은?

• W[i][j]는 도시 i에서 도시 j로 가기 위한 비용
• W[i][j] 는 W[j][i]와 다를 수 있다.
• 모든 도시간의 비용은 양의 정수이다.
• W[i][i]는 항상 0이다.
• W[i][j]=0는 도시 i에서 도시 j로 갈 수 없는 경우

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10)
다음 N개의 줄에는 비용 행렬이 주어진다.
각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다.

어떻게?

permutation 메소드를 이용한 풀이

1. 도시 방문 순열 생성
2. dfs 방문
3. 다음과 같은 조건을 만나면 되돌아감
   1. i에서 j로 갈 수 없는 경우 (비용이 0인 경우)
4. 이전 방문 비용을 변수에 저장 & 비교하여 min 값을 구하기 → 출력

• 풀이

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

from itertools import permutations
import sys
input = sys.stdin.readline

N = int(input())  # 2 <= N <= 10
W = [list(map(int, input().split())) for _ in range(N)]
permut = list(permutations(range(N)))   # 도시 방문 순서를 나타낸 순열
min_cost = 1000000 * 10


def dfs(N):
    global min_cost
    for p in permut:
        temp_total = 0
        for i in range(N):  # 시작도시와 도착도시의 인덱스 설정
            if (i == N-1):  # 처음 출발 도시로 돌아와야 하는 경우
                j = 0
            else:
                j = i+1
            temp_cost = W[p[i]][p[j]]
            temp_total += temp_cost
            if (temp_cost == 0) or (temp_total >= min_cost):
                j = N  # 갈수 없는 경우의 cost를 비교하지 않게 하기 위한 조건 설정
                break
		# 처음 출발 도시로 돌아온 경우, cost 비교
        if (j == 0) and (temp_total < min_cost): 
            min_cost = temp_total


dfs(N)
print(min_cost)

순열을 이용한 처음 풀이.
갈 수 없는 경우를 지정해서 걸러주는 것만 빼면 크게 까다롭지 않았으나, 시간을 좀 더 단축시키고 싶었다.
그래서 순열 사용하지 않은 두 번째 풀이.

일차원 배열을 이용한 방문 확인 + 백트래킹

1. visited 1차원 배열 정의
2. dfs 방문
   1. visited 확인 후 방문하지 않은 경우만 방문 (가장 작은 값을 먼저 방문하게 하는 것은 정답을 보장하지 못한다고 함)
   2. 방문한 경우 visited에 방문 표시 & 방문을 마치고 return 한 경우 방문 표시 해제
3. 다음과 같은 조건을 만나면 되돌아감 (※ 주의: 임시 비용 전역 변수를 두고 a += b 와 같은 방식을 이용했다면 되돌아갈 때 방문 해제하듯이 더한 비용 빼주는 처리도 필요함)
   1. i에서 j로 갈 수 없는 경우 (비용이 0인 경우)
   2. 돌아오는 경우가 아닌데 똑같은 도시 재방문
4. 다시 처음 출발 도시로 돌아온 경우
   1. min_cost 값과 비교하여 min 값 결정 → 출력

• 풀이

import sys
input = sys.stdin.readline

N = int(input())  # 2 <= N <= 10
W = [list(map(int, input().split())) for _ in range(N)]
visited = [0] * N
min_cost = 1000000 * 10


def dfs_visit(start, cost, visited):   
    global min_cost

    if (cost >= min_cost):
        return
    if (sum(visited) == N-1):
        if (W[start][0] != 0):
            min_cost = min(min_cost, cost + W[start][0])
        return

    for dest in range(1, N):
        if (W[start][dest] != 0) and (visited[dest] == 0):
            visited[dest] = 1
            # 비용 인수로 "이전 도시의 cost와 방문할 도시의 비용 합"을 전달
            dfs_visit(dest, cost + W[start][dest], visited)
            visited[dest] = 0


def dfs(N):
    for d in range(1, N):
        if (W[0][d] != 0) and (visited[d] == 0):
            visited[d] = 1
            dfs_visit(d, W[0][d], visited)
            visited[d] = 0


dfs(N)
print(min_cost)

처음에는 방문 해제하듯이 임시 비용 변수를 두고, 방문을 마칠 때마다 다시 비용을 빼주게끔 작성했었다. (아래처럼)
조금 복잡해보여서 위의 코드로 개선시켰다. (걸리는 시간은 둘 다 비슷하다.)

▼ 개선 전, 임시 비용 변수를 두고 방문 후 빼주는 풀이

import sys
input = sys.stdin.readline

N = int(input())  # 2 <= N <= 10
W = [list(map(int, input().split())) for _ in range(N)]
visited = [0] * N
min_cost = 1000000 * 10
tmp_cost = 0


def dfs_visit(start, visited):   # 목적지 도시 -> 시작 도시
    global min_cost, tmp_cost
    if tmp_cost >= min_cost:
        return
    if (sum(visited) == N-1):
        if (W[start][0] != 0):
            tmp_cost += W[start][0]
            if (tmp_cost < min_cost):
                min_cost = tmp_cost
            tmp_cost -= W[start][0]
        return

    for dest in range(1, N):
        if (W[start][dest] != 0) and (visited[dest] == 0):
            visited[dest] = 1
            tmp_cost += W[start][dest]
            dfs_visit(dest, visited)
            tmp_cost -= W[start][dest]
            visited[dest] = 0


def dfs(N):
    global tmp_cost
    for d in range(1, N):
        if (W[0][d] != 0) and (visited[d] == 0):
            visited[d] = 1
            tmp_cost += W[0][d]
            dfs_visit(d, visited)
            tmp_cost = 0
            visited[d] = 0


dfs(N)
print(min_cost)