[BOJ] 10971 외판원 순회2 - 파이썬

TIP

문제 링크 (opens new window)

목차

• 목차
• 문제 요약
• 문제 접근
• 풀이1. next_permutaions 구현
• 풀이2. itertools.permutations 이용
• 풀이3. DFS + Backtracking

문제 요약

• 1번 도시 ~ N번 도시
• 한 도시에서 시작해서 모든 도시를 거쳐서 다시 원래의 도시로 돌아와야한다. 단, 한번 갔던 도시로는 돌아올수없다.
• W[from][to] : from -> to
  • if 0, 길이 없다는 것
  • if not 0, from 도시에서 to 도시로 이동하는 비용

가능한 경로로 이동했을때 가장 적은 비용을 구하라.

문제 접근

n 이 10 이기때문에 모든 경우의 수를 탐색하는 알고리즘으로문제를 풀수있다. T(N) = N X N! = (경우 하나당 드는시간) X (N개의 도시를 나열하는 모든 경우의수) = 10 X 10! = 대략 3천 6백만

풀이1. next_permutaions 구현

TIP

BOJ 제출 현황/소스

PyPy3 220ms (opens new window)

Python3 1228ms (opens new window)

• 여기서 순열은 도시의 경로를 의미한다.
  • ex. [0, 1, 2, 3, 4] 는 0번 도시에서 1번도시, 2번도시, 3번도시, 4번도시를 차례로 이동한다는 것

1. 초기 순열 path = [0, 1, 2, ..., n]
2. 초기 ans = path 의 비용을 계산함. 만일 불가능한 경로라면 sys.maxsize 를 저장
3. next_perm(path) 로 다음 순열(도시 경로)를 구하고, calc_cost(..) 로 비용을 계산하여 최소 비용을 업데이트함. 마지막 순열을 계산할때까지 반복한다.

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    costs = [[0]*n for _ in range(n)]
    for i in range(n):
        s = list(map(int, input().split()))
        for j in range(n):
            costs[i][j] = s[j]

    path = list(range(0, n))
    ans = calc_cost(path, costs)

    while next_perm(path):
        if path[0] != 0:
            break
        ans = min(ans, calc_cost(path, costs))
    print(ans)

def next_perm(p):
    def swap(i, j):
        p[i], p[j] = p[j], p[i]
    n = len(p)

    i = n - 1
    while i > 0 and p[i-1] >= p[i]:
        i -= 1

    if i <= 0:
        return False

    j = n - 1
    while p[i-1] >= p[j]:
        j -= 1

    swap(i-1, j)

    # reverse
    j = n - 1
    while i < j:
        swap(i, j)
        i += 1
        j -= 1
    return True

def calc_cost(path, costs):
    ret = 0
    is_possible = True
    for i in range(len(path) - 1):
        from_, to_ = path[i], path[i+1]
        if costs[from_][to_] == 0:
            is_possible = False
            break
        ret += costs[from_][to_]
    ret += costs[path[-1]][path[0]]
    if not is_possible or costs[path[-1]][path[0]] == 0:
        return sys.maxsize

    return ret



main()

풀이2. itertools.permutations 이용

TIP

BOJ 제출 현황/소스

PyPy3 464ms (opens new window)

Python3 4520ms (opens new window)

• 여기서 순열은 도시의 경로를 의미한다.
  • ex. [0, 1, 2, 3, 4] 는 0번 도시에서 1번도시, 2번도시, 3번도시, 4번도시를 차례로 이동한다는 것
• itertools.permutations 로 순열을 구하고 비용을 계산한다.
• 비용을 계산할때 불가능한 경로라면 바로 break 하여 다음 순열로 넘어가도록 구현하였다. (이 최적화를 생략하여 제출했을때는 시간초과가 났다. )
  • 불가능한 경우1. costs[end_city][start_city] == 0
  • 불가능한 경우2. costs[from_city][to_city] == 0

import itertools
import sys
input = sys.stdin.readline
def main():
    n = int(input())
    costs = [[0]*n for _ in range(n)]
    for y in range(n):
        s = list(map(int, input().split()))
        for i in range(n):
            costs[y][i] = s[i]

    perms = itertools.permutations(range(n))
    ret = sys.maxsize
    for perm in perms:
        if costs[perm[-1]][perm[0]] == 0:
            continue
        cost = 0
        flag = True
        for i in range(n-1):
            from_v = perm[i]
            to_v = perm[i+1]
            if costs[from_v][to_v] == 0:
                flag = False
                break
            cost += costs[from_v][to_v]
            if cost >= ret:
                flag = False
                break
        if flag == False:
            continue
        cost += costs[perm[-1]][perm[0]]
        ret = min(ret, cost)

    print(ret)

main()

풀이3. DFS + Backtracking

TIP

BOJ 제출 현황/소스

PyPy3 144ms (opens new window)

Python3 96ms (opens new window)

• go(path, cost, visited)
  • dfs 탐색
  • path 에는 탐색 경로를 저장함
  • cost 에는 현재까지의 비용을 저장
  • visited 는 방문한 도시인지 체크하는 딕셔너리
• 백트래킹
  • 불가능한 경로일때 return
  • cost 가 현재까지의 최소비용보다 크거나 같다면 return
    • 왜냐하면 도시간의 비용은 무조건 양수이기때문에 현재 cost 에서 다음 도시를 방문한다고해도 최소비용이 될수없다.

import sys
input = sys.stdin.readline

def solve():
    # global : visited, ret
    visited[0] = True
    go(path=[0], cost=0, visit_cnt=1)
    
    print(ret)

# dfs+backtracking travasal function
def go(path, cost, visit_cnt):
    global ret
    # global : ret, costs, visited

    if cost >= ret:
        return

    last = path[-1]
    if visit_cnt == len(costs):
        # travasal finish

        start = path[0]
        if costs[last][start] != 0:
            ret = min(ret, cost+costs[last][start])
        return

    for i in range(1, n):
        if visited[i] or costs[last][i] == 0:
            continue
        visited[i] = True
        path.append(i)

        go(path,cost+costs[last][i],visit_cnt+1)
        
        visited[i] = False
        path.pop()
    return

n = int(input())
costs = [[int(_) for _ in input().split()] 
                   for y in range(n)]
visited = {city: False for city in range(n)}
ret = sys.maxsize

solve()