[DFS/BFS/완전탐색] ★ 10971번 - 외판원 순회 2(DFS, 완전탐색)

[백준] 10971번 - 외판원 순회 2

(한줄평) 설계자체는 단 시간에 했지만 시간초과를 해결하는데 시간이 오래걸렸던 문제로 꼭 복습 필요한 문제!!
이 문제는 외판원 순회 문제(TSP)로 N과 비용행렬이 주어졌을 때 외판원 순회에 필요하 최소 비용을 구하는 것이다. 1 ~ N 번호가 매겨진 도시들을 모두 거쳐 원래의 도시로 돌아오는 순회 여행을 말한다.
완전탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다.

풀이 시간: 90분 이내
1) 문제 해결 아이디어
<동작 과정>
1. 비용(graph) 입력 및 이동 경로(temp), 방문 여부(visited)를 저장할 리스트 생성
2. dfs(0, 0) 호출 -> 깊이= 0, 비용= 0으로 시작
3. n개 도시를 다 선택했고 마지막 도시→처음 도시로 가는 비용이 0이 아니라면 최소 비용 갱신(종료 조건)
4. 1 ~ n 번호의 도시 중 1개 선택하기
4-1. 첫번째 도시이면 바로 도시 선택
4-2. 이전에 방문한 적이 없고 해당 도시로 이동할 수 있고(비용이 0이 아님) 현재까지 비용(cost)가 최소 비용(min_cost)보다 작으면 도시 선택

첫번째 오류. 시간초과
10%까지 되다가 시간초과가 되었다.
1. 방문 체크를 할 때 not in temp로 했었는데 not in 연산이 시간이 오래걸리기 때문에 방문체크를 위한 리스트(visited)를 따로 만들고 그 값을 검사해주는 것으로 변경하였다. 하지만 여전히 시간초과가 되었다.
2. 원래는 이전 단계에서 선택했던 값이거나 현재 선택할 값으로 갈 방법이 없을 때만 제외했었다.
하지만 이 2가지 조건으로는 시간초과 문제를 효과적으로 해결할 수 없다.
중요한 점은 현재경로까지 비용(csot)가 최소비용(min_cost)보다 크면 더이상 탐색할 필요가 없다는 것이다!!! 이것을 깨닫지 못하면 시간초과를 절대 해결할 수 없는 문제였다.

[참고] https://ji-gwang.tistory.com/266

백준 10971번 파이썬 문제풀이(브루트 포스 - 외판원 순회 2)

2) 소스코드

import sys
input = sys.stdin.readline

# DFS(깊이, 비용)
def dfs(depth, cost):
  global min_cost
  # n개를 다 선택하면
  if depth == n:
    # 마지막 도시->시작 도시로 갈 수 있다면
    if graph[temp[n - 1]][temp[0]] != 0:
      min_cost = min(min_cost, cost + graph[temp[n - 1]][temp[0]])  # 최솟값 갱신
    return
  
  # 1~n 도시 선택하기(순열)
  for i in range(n):
    # 1. 첫번째 도시이거나
    # 2. 이전에 방문한적이 없고 해당 도시로 이동할 수 있고 최소 비용보다 작다면
    if depth == 0 or (not visited[i] and graph[temp[depth - 1]][i] != 0 and min_cost > cost):
      temp.append(i)      # i번 도시 선택
      visited[i] = True   # i번 도시 방문 처리
      # 현재 도시->선택 도시 비용을 더해서 넘겨줌
      dfs(depth + 1, cost + graph[temp[depth - 1]][i])
      temp.pop()          # i번 도시 선택 해제(원상복귀)
      visited[i] = False  # i번 도시 방문 처리 해제

n = int(input())  # 도시 수
# n개의 비용(도시 i->j로 가기위한 비용)
graph = [list(map(int, input().split())) for _ in range(n)]
temp = []       # 이동 경로
min_cost = 1e9  # 최소 비용
visited = [False for _ in range(n)]  # 방문 여부

dfs(0, 0) 
print(min_cost)