알고리즘 문제를 풀 때마다 TIL로 기록하기엔
- 하루에 푸는 알고리즘 문제의 양이 상당하고
- 모든 문제에서 wow timing을 느끼는 건 아니기에
지양하고자 했었다.
그런데 해당 문제는 풀면서 배우는 것이 한 두가지가 아니었기에, 늦은 밤 시간을 쪼개가며 TIL을 작성하고자 한다.
비트마스킹 기법을 배우기 전에 이게 뭐 그리 대단한 것인가 반신반의했었는데(그냥 0101 아니냐? :0)
완전탐색 및 dfs를 무작정 돌릴 수 없는 상황(노드 N>>10)에서 획기적인 아이디어(DP w/비트마스킹)를 제공하는 것에 매우 놀랐다.
-
왜 DP를 써야하는가?
이 문제에서 경로의 가지 수는 원순열의 가지 수와 같다. 그래서 시작 노드가 무엇이든 간에 상관없다는 건 한 눈에 알 수 있다.
문제만 놓고 봤을 때는 DFS 밖에 떠오르지 않았지만, 구글링+다수의 문제 시뮬레이션을 통해, '최단 경로를 구하는 과정에서 부분경로들을 계산하는 과정은 중복된다'는 핵심 아이디어를 얻을 수 있었다. 따라서 시간초과를 해결하기 위해 DP를 사용해야한다. -
비트연산자
2진수를 다루는 연산자를 제공해준다. 각 도시의 방문 여부를 0 or 1로 표현하며, 예시로 1번 도시와 4번 도시를 방문했다면 1001(2)로 표현되는 것이다.
&는 and를 의미한다.
1010 & 0110
-> 0010|는 or를 의미한다.
1010 | (1<<i)
-> ex: i가 2라면 1<<i는 0100을 의미하므로
-> 1010 | 0100
-> 1110아래는 코드이다. 너무 깔끔하게 코드를 작성하신 분의 것을 참조하여 내 것으로 만들었다. 감사합니다.
(코드출처: https://ji-gwang.tistory.com/448)
(비트연산자 개념참고: https://dojang.io/mod/page/view.php?id=2460)
N = int(input())
city = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1 for _ in range(1 << N)] for _ in range(N)]
def dfs(row, visit, start, cnt):
if cnt == N:
return 0
# 이미 해당 노선에 대해 최소비용이 계산되어 있다면 리턴
if visited[row][visit] != -1:
return visited[row][visit]
ret = 10000000
for i in range(N):
# 문법 : visit(이전에 방문했던 노드들)에 1<<i(1<<0이면 이진수 기준으로 1이므로 1번도시)
# (1<<1이면 이진수 기준 10이므로 2번도시...)
# 가 중복되거나, 현재(row)에서 i까지 가는 길이 막혀있다면,
# 해당 노드를 이미 방문했거나 연결되어있지 않다면
if visit & (1 << i) != 0 or city[row][i] == 0:
continue
# 마지막 방문 도시인데 처음도시를 선택하지 않았거나, 마지막 방문 도시가 아닌데 처음도시를 선택한 경우
if (cnt == N - 1 and i != start) or (cnt != N - 1 and i == start):
continue
ret = min(ret, dfs(i, visit | (1 << i), start, cnt + 1) + city[row][i])
visited[row][visit] = ret
return visited[row][visit]
print(dfs(0, 0, 0, 0))위 코드를 보면, '&'연산자는 '지금 방문한 도시에 혹시 방문한 적이 있는지' 여부를 체크하는 데에 사용하고,
if visit & (1 << i) != 0 or city[row][i] == 0: '|'연산자는 '다음 도시를 방문할 때에, 여태 방문했던 경로를 리턴할 때' 사용한다.
ret = min(ret, dfs(i, visit | (1 << i), start, cnt + 1) + city[row][i])visited 배열은 dp 값을 기록하는 배열이다.
visited[row][visit]의 의미는 다음과 같다. 쉽게 예시를 들어서 설명하자면,
visit의 도시들을 거쳐왔고, 현재 도시(row)에서 출발했던 도시(index가 0인)로 다시 돌아가는 데에 걸리는 최소 비용
visited[2][4] : 도시 3(index로는 2)에서 3을 거쳐왔고, 다시 출발했던 도시로 돌아가는 데 걸리는 최소 비용
최종적으로는 visited[0][0] (0번째 도시(문제 상에서 1번 도시)에서 출발하며, 아직 방문한 도시가 없는 상태에서, 0번째 도시로 다시 가는 데에 드는 최소 비용) 을 리턴하게 된다.
