[Python] 백준 10971 외판원순회2 - 완전탐색, DFS, 시간복잡도 개선

<10971 외판원 순회2>

 

 

외판원이 원을 둘러싼 뭔가 판인가.. ? 했는데

외부 판매원이었다 하하하

뭔가 예에에에에전에 번역한 문제를 typical하게 불러서 가끔 용어가 이상한게 있는 것 같다.

Traveling Salesman Problem (TSP) 라고 부른다고 함. 보부상 문제라고 하면 좋을 것 같음ㅋㅋㅋㅋㅋ

팀원의 말에 의하면 GPT도 가장 어려운 알고리즘 문제중에 하나로 꼽는,,, 그런 문제다.

 

 

 

처음에 문제만 읽고 대충 구조는 짰는데, 첫번째 도시와 마지막 도시 처리하는 부분에서 애를 먹었다.

결국 여러 블로그를 참고해서 가장 이해가 잘 가는 코드를 기반으로 수정했다.

아직.. 난이도 실버 문제를 혼자 맞추기는 어렵다.

그래도 대충 구조 자체는 짤 수 있어서 일주일 만에 엄청난 성장을 했다!

 

아래 코드로 제출함.

 

첫번째 코드

# 외판원 순회2
import sys

def travel(cnt, start, now, cost):
  global min_price

  if cnt == n and city[now][start] :
      cost += city[now][start]
      if cost < min_price:
        min_price = cost
        return

  for i in range(n):
    if not visited[i] and city[now][i]:
      visited[i] = True
      travel(cnt+1, start, i, cost+city[now][i])
      visited[i] = False

n = int(sys.stdin.readline())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [False] * n
min_price = sys.maxsize

for i in range(n):
    visited[i] = True
    travel(1, i, i, 0)
    visited[i] = False

print(min_price)

 

근데 백준을 보니 내 코드는 소요시간이 4300ms 인데 44ms로 줄여서 짠 분이 계셨다.

위 코드에서 보면

아래 travel 함수를 처음 호출할때 for문을 돌리고 함수 안에도 for 문이 있어서 시간복잡도가 O(n^2)인 것을 알 수 있다.

근데 첫번째 도시만 처리를 잘하면 굳이 이중 for문을 돌릴 필요가 없어 보인다. (!)

 

제일 처음 부분에서 그럼 visitied[0] = 1을 설정하고 다음 도시로 가면 된다.

즉, 첫번째 도시는 무조건 시작점이므로 방문한 것으로 치고 시작하면 된다.

그리고 시작점은 비용이 0이므로 비용도 0으로 시작하면 된다.

 

수정한 코드는 아래와 같다.

 

두번째 코드

# 외판원 순회2
import sys

def travel(cnt, start, now, cost):
  global min_price

  if cnt == n and city[now][start] :
      cost += city[now][start]
      if cost < min_price:
        min_price = cost
        return

  for i in range(n):
    if not visited[i] and city[now][i]:
      visited[i] = True
      travel(cnt+1, start, i, cost+city[now][i])
      visited[i] = False

n = int(sys.stdin.readline())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [False] * n
min_price = sys.maxsize

visited[0] = 1
travel(1, 0, 0, 0)

print(min_price)

 

 

이랬더니 소요시간이 484ms로 줄었다.

44ms... 어떻게 갈 수 있을까?

 

핵심은 가지치기 다!

소요시간이 짧은 코드를 컨닝해보니,

if문으로 cost를 비교하기 전 이전 도시까지 방문한 비용이 만약에 min_price보다 크다면 이미 비용을 초과했기 때문에 계산할 필요 없이 종료한다.

그리고 이 과정에서 start도 굳이 필요없는 파라미터라는 것을 알게 되었다.

start를 넣었던 이유는 마지막 위치에서 start로 갈 수 있느냐를 검증하기 위함이었다.

이는 그냥 now에서 1번째 도시로 갈 수 있느냐로 작성하면 되는 것이었다.

city[now][0] != 0:

 

최종 코드는 아래와 같다.

 

 

최종 코드

# 외판원 순회
import sys

def travel(cnt, now, cost):
  global min_price

  if min_price <= cost:
    return

  if cnt == n and city[now][0] != 0:
      min_price = min(min_price, cost+city[now][0])
      return

  for i in range(n):
    if not visited[i] and city[now][i]:
      visited[i] = True
      travel(cnt+1, i, cost+city[now][i])
      visited[i] = False

n = int(sys.stdin.readline())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [False] * n
min_price = sys.maxsize

visited[0] = 1
travel(1, 0, 0)

print(min_price)

 

 

결국 시간복잡도를 O(n^2) ➔ O(n) 으로 줄이고, 

실제 소요시간도 4300ms ➔ 44ms로 개선할 수 있었다.