[실버2] 10971번 : 외판원 순회2

🛠 문제

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

👩🏻‍💻 해결 방법

dfs를 통해 출발 가능한 모든 경우의 수를 하나씩 탐색하도록 작성했는데 시간초과가 나서 해결할 수 없었다...

소스 코드

import sys
input = sys.stdin.readline 

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

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

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
result = 1000001
for i in range(n):
  visited = [False] * n
  dfs(i, i, 0, [i])

print(result)

💡 다른 사람의 풀이

DP와 비트마스크를 이용한 해결 방법이다
풀이가 어려우므로 완벽히 이해할 때까지 복습이 필요하다!
외판원 순회 문제 참고 url : https://withhamit.tistory.com/246

import sys

def find(now, before):
    # 남아있는 경로를 이미 방문한 적이 있음
    if dp[now][before]:
        return dp[now][before]
        # 모두 방문한 경우
    if before == (1<<n) - 1:
        return path[now][0] if path[now][0] > 0 else sys.maxsize

    # 현재 지점에서 이동할 수 있는 지점들을 탐색
    cost = sys.maxsize
    for i in range(1, n):
        # before가 다른 노드를 방문한 적이 있고, 이동하려는 지점이 이동 불가할 때
        if not (before>>i)%2 and path[now][i]:
            # i부터 0까지 순회를 만든 최소 비용
            tmp = find(i, before|(1<<i)) #before | (1<<i) == before + (1<<i) == before에 i값 십진수 변환 후 추가
            # (now~i), (i~0)의 합과 현재까지의 최소 비용과 비교
            cost = min(cost, tmp + path[now][i])

    # 메모이제이션
    dp[now][before] = cost
    return cost


n = int(sys.stdin.readline())
path = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*(1<<n) for _ in range(n)]

print(find(0, 1))