짧은 글쓰기
팩트를 전하는 것은 옳은가? 팩트를 잘 포장해야 하는건지도 잘 모르겠다. 그저 듣고 그 속에 담긴 진심(팩트)만을 받아들이기를 바란다. 그렇지만 그러기 쉽지 않다는건 나도 안다. 나도 잘 보이고 싶어서 한 말이 아니기 때문에 그 결과를 겸허히 받아들여야 하겠지.
왜냐하면, 이건 "내가 어떤 어른이 되고싶은가"에 대한 결론이기 때문이다. 나는 아직 '어른'이 아니라 생각한다(성인은 맞다). 내가 생각하는 어른은 자신의 상황이 어떠하든 주위 사람들을 돌볼줄 아는 사람이다. 그렇기 때문에 내 행동에 후회는 없다만, 시간이 지나봐야 스스로도 오늘의 일을 평가할 수 있을 것 같다.. 당분간은 잊고 공부만 하자!
알고리즘 문제 풀이
2098 외판원 순회
알고리즘 문제도 잘 푸시고 예쁘신 이주희님의 풀이를 보고 직접 풀어본 결과를 정리한 글입니다.
- 개요
2098 외판원
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다.
여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다)
이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다.
W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다.
즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다.
W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.
입력
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
출력
35
- 추상화
최소 경로 비용이라는 최적의 값이 있는 문제이며, 싸이클이 있기 때문에 A-B-C-D-A로 돌아오든, B-C-D-A-B로 돌아오든 총 비용에는 변함이 없습니다.
그렇기 때문에 다중트리로 경우를 나누어 A-B, A-C, A-D의 경우로 나누고, A-B의 경우는 A-B-C, A-B-D의 경우로 계속 나누어 각 경우의 해를 구하면 됩니다.
- 구체화
싸이클이 있기 때문에 A에서 출발하는 것으로 고정합니다.
N개의 도시가 존재하기 때문에 입력받은 N만큼의 빈 리스트를 생성하고, N개 만큼의 가중치(비용)을 담습니다.
DFS의 방식으로 각 경우를 순회하는데 한번 들른 도시는 다시 들를 수 없으므로 visited를 만들어 체크합니다.
DFS이기 때문에 2중 리스트에서 now, next를 2중 for문으로 탐색합니다.
경로에 따른 cost를 담으며 재귀하고, min_cost를 반환하여 두 값의 크기를 비교하여 더 작은 값을 최소경로비용으로 담게 됩니다.
dp에 담긴 정보는 경로에 따른 비용이므로(총 16개 생성됨) 재귀할 때 기억하며 저장합니다.
- 비트마스크(bitmask)
visited라는 이중 리스트를 생성할때의 공간 복잡도(메모리 크기)를 줄이기 위해 사용합니다.
여기서 비트 연산자와 비교 연산자가 사용됩니다.
예를들어 visited == (1 << N) - 1 라는 구문에서는 visited가 3(0011)이고 1 << N은 1(0001)을 N(3이라고 가정)만큼 왼쪽으로 이동합니다. 그러면 8(1000)이 됩니다. 그 뒤 1을 빼줍니다.
visited & (1 << next)은 visited(7 가정)와 next(2가정)만큼 1을 왼쪽으로 쉬프트한 값의 and 연산을 진행하여 0111과 0010의 and인 0010을 반환합니다.
import sys
N = int(input())
world = []
for _ in range(N):
world.append(list(map(int, sys.stdin.readline().split())))
dp = {}
def DFS(now, visited):
if visited == (1 << N) - 1:
if world[now][0]:
return world[now][0]
else:
return int(1e9)
if (now, visited) in dp:
return dp[(now, visited)] # now까지 방문한 최소 비용
min_cost = int(1e9)
for next in range(1, N):
# 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
if world[now][next] == 0 or visited & (1 << next):
# &는 비트연산자. AND 연산한 값을 반환함
continue
cost = DFS(next, visited | (1 << next)) + world[now][next]
# 비트 or 연산자, visited와 (1 << next)를 비트 단위에서 연산
min_cost = min(cost, min_cost)
# visited를 dp 배열로 만들기
dp[(now, visited)] = min_cost # 현재도시까지 방문한 경우 중에서 최소 비용이 드는 루트의 비용 저장
return min_cost # 현재도시까지 방문하는 비용 리턴
print(DFS(0, 1)) # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리