| 시간 제한 | 메모리 제한 |
| 1초 | 256MB |
문제
고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.
순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’
현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하지만, 태양이는 나머지 4명을 모두 이기는 방법이 생각이 나지 않는다. 태양이를 도와 꼬리를 무는 선수 나열을 만드는 프로그램을 작성하여라.
입력
첫째 줄에 N이 주어진다. (2 ≤ N ≤ 20)
둘째 줄부터 N개의 줄에는 N개의 정수가 주어지는데, p+1번째 줄의 q번째 수는 아래 규칙을 만족한다.
- p번 선수가 q번 선수를 이겼으면 1.
- p번 선수가 q번 선수에게 졌으면 0.
- p = q인 경우 0.
단, 태양이는 1번 선수이다.
출력
첫 번째 줄에는 꼬리를 무는 선수 나열의 최대 길이 L을 출력한다.
두 번째 줄에는 꼬리를 무는 선수 나열 S1 S2 … SL을 출력한다. 꼬리를 무는 선수 나열은 다음과 같은 규칙을 만족해야 한다.
- S1 = 1
- S1, S2, …, SL는 서로 다르다.
- 모든 1 ≤ i ≤ L-1에 대해서 Si번 선수는 Si+1번 선수를 이겨야 한다. 다만, SL번 선수가 S1번 선수를 이겨야 할 필요는 없다.
풀이
단순하게 접근해서 1에서 출발, 가장 긴 탐색을 기록한 dfs의 경로를 반환하도록 코드를 짜봤습니다.
n = int(input())
link = [list(map(int, input().split())) for _ in range(n)]
res = [1]
def tsp(bit, route, depth):
for i in range(n):
if link[route[-1] - 1][i] and not(bit & (1 << i)):
tsp(bit + (1 << i), route + [i + 1], depth + 1)
else:
global res
if len(route) > len(res):
res = route
tsp(1, [1], 1)
print(len(res))
print(*res)짜고 나서 생각해보니 시간복잡도가 대충 O(N!)인데, N이 최대 20인 걸 생각해보면 2,432,902,008,176,640,000이라는 어마어마한 탐색 경로가 나옵니다. 1번 선수부터 방문한다고 정해졌으니 엄밀하게 따져보면 O((N-1)!)에다가 두 선수의 연결 관계가 반드시 승 또는 패로 갈리기 때문에 양방향 탐색이 성립하지 않으므로 가짓수는 더 줄어들겠지만, 어쨌든 시간 내에 해결은 어려워 보이죠?
문제 분류를 열어보니 외판원 순회 문제(TSP)입니다. 아주 대표적인 NP-Hard로 분류된 문제이고, 저는 이걸 공부 안해서 잘 모릅니다. 망했네요. 뭐 대강 찾아보니 다항시간 안에 해결할 수 있는 방법이 아직 없고 다항시간에 해결이 가능한지, 불가능한지 조차 증명이 안되었다는데 다항시간에 해결이 불가능함을 증명하는 것으로 100만 달러의 상금을 얻을 수 있다는 흥미로운 이야기는 기억에 남네요.
TSP의 정석적인 해결 방법은 크게 두 가지로 나뉩니다. 먼저 동적계획법으로 중복 연산 줄이기, 나머지는 백트래킹을 이용한 분기한정입니다. 둘 다 지수시간으로 해결할 수 있는 방법이지만 분기한정은 유망구조 판단이 어려우니 패스. 동적계획법으로 해결해볼게요. 여기서 중복 연산이라 함은 서로 다른 경로를 두고 보았을 때 일부분의 탐색 순서가 겹치는 경우가 있습니다. 이런 경우, 한 쪽에서 탐색했던 일부분을 끌어쓰면 연산을 줄일 수 있겠죠. 이걸 활용합니다.
다만 기존의 TSP문제는 모든 정점을 다 돌아야 하지만, 이 문제는 그렇지 않습니다. 1번 선수인 태양이에서 출발하기만 하면 되고 모든 선수를 다 순회할 필요가 없습니다. 가능한 순회 경로 중 가장 긴 것을 찾아야 하기 때문에 모든 간선의 가중치를 1로 설정하고 가중치가 큰 쪽을 최적해로 선택해 나가는 식으로 해를 구성하면 될 것 같습니다. 탐색 여부는 비트마스크로 관리하면 좋을 것 같고요.
그럼 부분 해를 관리할 2차원 배열을 만들어서 정의해봅시다. i는 현재 방문 중인 선수의 번호, v는 현재까지 탐색한 선수를 관리하는 비트 값입니다.
dp[i][v] = i번째 선수로부터 v를 제외한 선수를 순회할 때 가장 긴 순회 경로의 길이
이렇게 해두고 나중에는 비트 값으로 경로를 재탐색해 가장 긴 꼬리를 무는 선수 나열을 뽑아내도록 합니다.
정답 코드
import sys
input = sys.stdin.readline
n = int(input())
link = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (1 << n) for _ in range(n)]
def tsp(now, visit):
if dp[now][visit] == 0:
for i in range(n):
if link[now][i] == 0 or visit & (1 << i): continue
dp[now][visit] = max(dp[now][visit], tsp(i, visit | 1 << i) + 1)
return dp[now][visit]
def trace(now, visit, route):
for i in range(n):
if link[now][i] == 0 or visit & (1 << i): continue
if dp[now][visit] == dp[i][visit | (1 << i)] + 1:
trace(i, visit | (1 << i), route + [i + 1])
break
else:
print(*route)
print(tsp(0, 1) + 1)
trace(0, 1, [1])
