728x90
2098. 외판원순회
난이도 : 골드 1
소요 시간 : 45분
날짜 : 2024.12.22
언어 : 파이선
알고리즘 유형 : 비트마스킹, dp, dfs
설명 보기전에 문제 풀어보러 가기
1. 문제 설명
- n 개의 도시가 주어진다.
- 도시의 연결은 비용으로 연결된 비대칭그래프이다.
- 최소의 비용으로 모든 도시를 순회하고 돌아와야 한다.
2. 해결 방식
비트마스킹과 DP....(그리고 dfs)
- DP 배열 설명 : dp는 2차원 배열로써 dp[i][j] 는 도시 i에 도달했고, 방문 상태 j 일 때의 최소비용을 나타낸다.
- 비트마스킹 : 방문 상태 j 는 비트마스킹으로 나타낸다. n의 범위가 2 < n < 16 이므로 비트를 사용하기 충분하다.
- dfs에서의 가지치기
3-1. 모든 도시를 방문 한 경우 : 최소값을 갱신할 수 있다.
3-2. 최소비용이 이미 있는 경우 : 그 값을 재사용한다. - dfs에서의 점화식
4-1. 식
4-2. 설명 : 다음 도시로 이동하면서, 다음도시를 방문처리한다. 현재경로 비용 , 다음 경로의 비용의 최소값을 구한다.dp[now][visit] = min(dp[now][visit], arr[now] + dfs(next, visit | (1 << next))
- 함수 실행 dfs(1, 0)
- 모든 점을 순회하는 사이클이기 때문에 어느 점에서 시작해도 상관없음.
- 시간복잡도 : O(n * 2^n) -> 최대 100만
3. 정답 코드
import sys
sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")
# input = sys.stdin.readline
inf = 1e10
n = int(input()) # 2 < n < 16
arr = [list(map(int, input().split())) for _ in range(n)] # 비대칭 그래프
dp = [[-1] * (1 << n) for _ in range(n)] # dp[i][j] : i 에 도달, k = visited인 최소 비용
def dfs(now, visit):
if visit == (1 << n) - 1: # 모든 도시 방문
return arr[now][0] if arr[now][0] > 0 else inf
# 최소비용 이미 있음 -> 재사용
if dp[now][visit] != -1: return dp[now][visit]
dp[now][visit] = inf
for next in range(1, n):
if arr[now][next] == 0:continue # 경로가 없음
if visit & (1 << next):continue # 이미 방문함
# 점화식 - 재귀
# 1. 현위치(now)에서 다음도시(next)로 이동
# 2. 방문처리, 최소비용 있는 경우 이미 위에서 체크함
# 3. dfs + 재귀 -> 비용 갱신
dp[now][visit] = min(
dp[now][visit],
arr[now][next] + dfs(next, visit | (1 << next))
)
return dp[now][visit]
# 사이클이기 때문에 시작을 0으로, 0을 방문 -> visit = 1
res = dfs(0, 1)
print(res)
반응형
'백준 문제풀이 코드저장소 > Gold' 카테고리의 다른 글
Baekjoon 2143. 두 배열의 합 / Python (0) | 2024.12.23 |
---|---|
Baekjoon 15681. 트리와 쿼리 / Python (0) | 2024.12.23 |
Baekjoon 1562. 계단 수 / Python (0) | 2024.12.21 |
Baekjoon 7453. 합이 0인 네 정수 / Python (0) | 2024.12.20 |