TSP 라고 하는 알고리즘의 기본형 문제라고 한다.
DFS + DP + 비스마스킹을 이용해서 푸는 문제인데
DP도 아직 어렵고, 비스마스킹도 익숙하지 않아서 풀이를 이해하는데 애를 먹었다.
제출코드
import sys
input = sys.stdin.readline
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
inf = 1 << 31
DP = [[0] * (1<<N) for _ in range(N)]
def dfs(now, visited):
if visited == (1 << N) -1:
if not graph[now][0]:
return inf
DP[now][visited] = graph[now][0]
return graph[now][0]
if DP[now][visited] != 0:
return DP[now][visited]
DP[now][visited] = inf
for i in range(1, N):
if visited & (1 << i) or not graph[now][i]:
continue
DP[now][visited] = min(DP[now][visited], dfs(i, visited | (1 << i)) + graph[now][i])
return DP[now][visited]
dfs(0, 1)
print(DP[0][1])코드를 하나하나 뜯어보자.
inf = 1 << 31 DP = [[0] * (1<<N) for _ in range(N)]
inf값은 임의의 큰수를 넣어 DP값을 초기화 하기위한 변수다. 하지만 DP = [[inf] * (1<<N) for _ in range(N)] 이런식으로 DP배열을 초기화 했다면 시간초과가 날 것이다.
DP 배열은 2차원으로 들어간다.
DP[i][j] = 100 값의 의미는 현재 위치가 i이고, 방문한 도시의 상태가 j 일때 i에서 남은 도시를 다 방문하고 출발점으로 돌아오기까지의 최소 거리가 100 이라는 뜻이다.
처음 부터 어렵다.
우선 j 부터 보자 j는 N개의 도시들중 지금까지 방문한 값을 나타내야하기때문에 여기서 비트마스킹을 사용한다.
j 값이 1011101(2) 라면 도시는 총 7개가 있고 아직 방문하지 않은 도시는 1, 5 번 도시이다. (0번 도시부터 시작한다.)
예시를 보자. N = 7 일때
c1. DP[4][1001101(2)] 의 의미를 살펴보자.
현재 위치가 4이고 방문하지 않은 번호가 1, 4, 5 이다.
이상하다
현재 위치가 4번인데 4번이 방문하지 않은 도시라고 나온다. 그래서 이경우는 처리하지 않는다..!
c2. DP[4][1001101(2)] = 40 을 보자
현재 위치 4, 방문하지 않은 도시 1, 5번이다.
이 상황에서 모든 경우의 수를 다 봤을때 출발점까지 되돌아 오는 가장 작은 비용이 40 이라는 뜻이다.
출발점을 0번이라고 가정해보면
경우의 수는 다음과 같다.
0 - ? - ? - ? - 4 - 1 - 5 - 0 ... 1번
0 - ? - ? - ? - 4 - 5 - 1 - 0 ... 2번i == 4 이므로
4 - 1 - 5 - 0
4 - 5 - 1 - 0
이 둘 중 가장 작은 비용이 40 이라는 뜻이다.
하나만 더 살펴보자. N = 4 이고
c3. DP[2][0100(2)] = 10 이다.
이경우는 출발점이 2이다.
왜냐? 2번 빼고 다 방문하지 않았으니깐
이때 경우의 수는
2 - 0 - 1 - 3 - 2
2 - 0 - 3 - 1 - 2
2 - 1 - 0 - 3 - 2
2 - 1 - 3 - 0 - 2
2 - 3 - 0 - 1 - 2
2 - 3 - 1 - 0 - 2이고, 이중 가장 작은 값이 20이 되겠다.
그리고 그 20이 정답이된다.
출발점이 어딘지는 중요하지 않다. 왜냐하면 어짜피 모든 도시를 다 돌아서 싸이클을 만들 것이기 때문이다.
그러면 DP 는 어떻게 적용 될까?
N = 4 이고, 출발점이 0인 경우를 보자.
DP[0][0001(2)] = min(DP[0][visit], DP[x][visited] + graph[0][x]) (1개 방문)
dfs 재귀 DP[x][visit] = min(DP[0][visit], DP[x][visited] + graph[x][y]) (2개 방문)
dfs 재귀 DP[y][visit] = min(DP[y][visit], DP[z][visited] + graph[y][z]) (3개 방문)
dfs 재귀 DP[z][visit] = graph[z][0] (4개방문)
이렇게 마지막 값에서 부터 올라가며 가장 작은 값을 적용하게 된다.
DP 이해가 끝났다면 이후는 나름 수월하다.
def dfs(now, visited): if visited == (1 << N) -1: if not graph[now][0]: return inf DP[now][visited] = graph[now][0] return graph[now][0] # ...(중략)
if visited == (1 << N) -1
모든 도시를 방문했을때, 즉 방문값이 11111(2) 일 경우릐 처리를 해준다.
1<<N 의 경우 이진수 표현값은 100000(2) (N+1)자리수 이고
(1<<N) -1 의경우 이진수 표현값은 11111(2) N자리이다.
비트마스킹을 이용해 방문값을 처리해줄때 많이 유용하게 자주 쓰일거 같으니 기억해 두자!
다시 문제로 돌아와서 모든 도시를 방문했다면 다시 출발점으로 돌아가야 한다. 출발점을 0으로 정했으니 graph[now][0] 을 확인해서..
1. graph[now][0] == 0 이라면 길이 없으므로 inf 리턴!
2. graph[now][0] != 0 이라면 DP배열에 저장후, graph[now][0]을 리턴!
다음은 계산이 필요없는 경우를 고려한다.
# 중략 .. if DP[now][visited] != 0: return DP[now][visited] DP[now][visited] = inf # 중략 ..
DP 배열을 초기에 0으로 초기화 했기 때문에 DP[now][visited] != 0 이라면 이미 계산된(최소값이 반영된) 상태이기에 고려하지 않는다.
반대로 0이라면 계산이 필요하고 우리는 최소값으로 갱신할 것이기 때문에 임의로 만들어 놓은 큰 수 inf 를 할당해준다.
이제 방문안한 도시들을 차례로 방문할 차례이다.
# 중략... for i in range(1, N): if visited & (1 << i) or not graph[now][i]: continue # 중략...
위에서 말했듯이 1 << i 는 1000(2) (x+1 자리수) 형태로 나타나진다.
앞서 도시번호를 0부터 시작했기 때문에 i 를 그대로 쓰면되고
visited 와의 AND 연산을 통해 visited 의 i+1번째가 0인지 1인지 알 수 있다.
연산결과가 1이면 visitedd의 i+1번째가 1이고 0이면 0일것이다.
또한 graph[now][i] 가 0이라면 now 도시에서 i 도시로 갈수 없다는 의미이다.
즉 i 번째를 이미 방문했거나 visited & (1 << i),
now에서 i로가는 길이 없다면 graph[now][i] == 0
i 번째 도시는 건너뛰고 다음을 본다.
마지막으로 DP 배열 값을 갱신하자
DP[now][visited] = min(DP[now][visited], dfs(i, visited | (1 << i)) + graph[now][i])
이 부분은 그러면 DP 는 어떻게 적용 될까? 부분의 예시를 참고하자.
끝
dfs(0, 1)
끝으로 함수를 호출하여 배열을 채우자
출발점은 0으로 가정했으니 now : 0 이고
visited 값은 0번 도시가 방문처리된 1 == 00...001(2) 이 들어간다.
만약 출발점은 x번 도시로 하고 싶다면
dfs(x, 1 << x) 로 표현해주면 된다!
