백준 10971 외판원 순회 2

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

10971번: 외판원 순회 2

📌 해결순서

처음에는 각 도시에서 다음 도시로 가는 비용이 가장 싼 경우 + 그 다음도시를 아직 방문하지 않은 경우에 대해서만 탐색을 했는데 틀려서 완탐으로 풀어야 하는 문제겠구나 생각했다

우선, 0번째 도시에서 출발해서 다시 0번째로 돌아오는 순회구조를 트리로 그려보면 이렇다.

 

0번째 도시에서 출발해서 다시 0번째 도시로 돌아오는 경우는 이렇게 6가지다.

백트래킹을 사용하여 dfs 완탐을 한다면 함수 호출구조를 이렇게 생각할 수 있다.

 

dfs(start, next, value, visited)

 

dfs(0, 0, 0, [0])

↓

dfs(0, 1, 10, [0, 1])

↓

dfs(0, 2, 19, [0, 1, 2])

↓

dfs(0, 3, 31, [0, 1, 2, 3])
순회를 마쳤으므로 pop을 통해서 방문한 도시를 visited에서 제거해준다.

↓

dfs(0, 3, 20, [0, 1, 3])

↓

dfs(0, 2, 29, [0, 1, 3, 2])

 

모든 경우에 대해 순회를 마칠때까지 이 구조의 dfs를 반복호출한다.

 

1. 도시의 갯수만큼 dfs 함수를 호출한다

2. 다음도시로 갈수 있고 (w[next][i]  != 0) , 아직 방문하지 않는도시이고, 시작도시와 다음도시가 다르다면 append 후 dfs 탐색을 계속 진행한다.

3. 모든 도시를 순회했다면 시작도시로 돌아가는 비용을 더하고 이전 순회코스의 비용과 비교해서 적은 값으로 갱신

4. pop을 해주고 다음 도시에 대해서 반복

📌 코드

import sys
input = sys.stdin.readline

n = int(input())
w = [list(map(int, input().split())) for _ in range(n)]
res = sys.maxsize


def dfs(start, next, value, visited):
    global res

    if len(visited) == n:
        if w[next][start] != 0:
            res = min(res, value + w[next][start])
        return

    for i in range(n):
        if w[next][i] != 0 and i not in visited and i != start:
            visited.append(i)
            dfs(start, i, value + w[next][i], visited)
            visited.pop()


for i in range(n):
    dfs(i, i, 0, [i])

print(res)