백준: 10971 외판원 순회 2

문제

10971번: 외판원 순회 2

 

문제 풀이

 이 문제는 각 도시에 대해 가중치가 주어질 때 모든 도시를 순회하되, 최소 값으로 순회하는 경우의 수를 찾는 문제이다. 보통 이러한 문제는 DFS를 통해 방문한 경로를 기록해두고, 가능한 경로를 모두 탐색하는 방식으로 푼다. 다른 방법으로는 1 - 2 - 4 - 3 - 1과 같은 방문 순서를 순열로 구한 후에 계산하는 방식도 있을 수 있다.

 하지만 순열을 계산하고 처리하는 것은 익숙하지 않아, DFS로 방문 가능한 경로를 탐색하고, 재귀 호출의 depth가 0이 되면 방문한 경로의 값을 기록하도록 하였다. depth가 0이 된다는 것은 다시 원점으로 돌아왔다는 것을 의미한다.

 

 

코드

DFS를 이용한 풀이

from sys import stdin


def dfs(cur_node, cost):
    global answer

    if not cur_node and all(visited):
        answer = \
            cost if answer is None else min(answer, cost)
    else:
        for next_node in range(n):
            if cities[cur_node][next_node] and not visited[next_node]:
                visited[next_node] = True
                dfs(next_node, cost + cities[cur_node][next_node])
                visited[next_node] = False

if __name__ == '__main__':
    answer = None
    n = int(stdin.readline())
    cities = [list(map(int, stdin.readline().split())) for _ in range(n)]
    visited = [False] * n
    dfs(0, 0)
    print(answer)

 Python3로 제출할 경우 시간초과가 발생한다. PyPy3로 제출하면 시간 내에 통과하며 문제를 해결 할 수 있다.