오랜만에 외판원 순회 문제를 풀어보았다. 이름부터 벌써 재밌다. 포켓몬에 관한 문제이기 때문.

BOJ 16385 - Pokemon Go Go 링크
(2022.09.30 기준 G1)
(치팅하면 피카츄한테 감전됨)

문제

포켓몬과 그 포켓몬의 위치가 n개 주어진다면, (0, 0)에서 시작하여 모든 포켓몬의 종류를 잡고 다시 (0, 0)으로 돌아올 때 최단 거리

알고리즘

시작점에서 거쳐야 하는 경유지를 모두 거쳐서 시작점으로 되돌아 오는 경우이므로 외판원 순회

풀이

문제의 예제를 먼저 살펴보자.

5마리의 포켓몬이 이렇게 위치해있다는 것이다.
이 문제는 모든 포켓몬을 잡는 것이 아니라, 포켓몬의 종류마다 한 마리씩만 잡으면 되는 것이다. 그러므로

이런 루트가 나올 것이다. (20, 20)에 있는 Flareon은 (1, 1)에서 잡을 수 있으니 패스하는 것이다.

그러니깐 결국은 무슨 말이냐면, 포켓몬의 종류마다 고유 번호를 붙이자 (해시)
그러면 모든 포켓몬마다 고유 번호가 생긴다. (같은 종류이면 같은 번호)
그 고유 번호를 포켓몬의 입력 순서(인덱스)에 따라 저장해두고
모든 포켓몬끼리 거리를 저장한 다음에, 외판원 순회를 돌린다. 그 때, 방문 체크는 모든 포켓몬이 아니라 포켓몬의 종류로 하면 된다. 당연히 dp의 크기는 가로는 (1 << (포켓몬의 종류 수)), 세로는 모든 포켓몬의 수가 된다.

좌표 TSP를 보고 겁먹지 말자. 그냥 거리를 저장하고 알고리즘 돌리면 된다.
거기에 해시가 추가된다고 더 어려워지고 그러진 않는다.

코드

import sys; input = sys.stdin.readline
from math import inf
from collections import defaultdict

def dfs(here, v):
    if v == (1 << pokemon_unique) - 1:
        return distance[here][0]
    if dp[here][v] > -1:
        return dp[here][v]
    dp[here][v] = inf
    for there in range(n + 1):
        if not v & (1 << pokemon_idxToId[there]): # 잡히지 않은 포켓몬 종류일 경우
            dp[here][v] = min(dp[here][v], dfs(there, v | (1 << pokemon_idxToId[there])) + distance[here][there])
    return dp[here][v]

n = int(input())
# 포켓몬 종류당 한 마리씩만 잡으면 되므로 모든 포켓몬을 잡을 필요가 없음
# 그러므로 포켓몬 종류마다 고유 번호를 붙여준다. (해시)
# 그리고 입력되는 순서대로 그 포켓몬의 고유 번호와 위치를 저장하고
# 전에 입력된 포켓몬들과의 거리를 저장하자.
pokemon_unique = 1 # 포켓몬 종류 수. (0, 0)에서 시작해야 하므로 (0, 0)도 하나의 포켓몬이라 생각하면 편하다.
pokemon_id = defaultdict(int) # 포켓몬 종류마다의 고유 번호
pokemon_idxToId = [0] # 포켓몬들의 고유 번호. (0, 0)의 고유 번호는 0번으로 하자.
pokemon_pos = [[0, 0]] # 포켓몬들의 위치. (0, 0)의 위치도 저장하자.
distance = [[inf] * (n + 1) for _ in range(n + 1)] # 포켓몬 + (0, 0) 이므로 총 n + 1개가 있다.
for i in range(1, n + 1): # 포켓몬은 1번부터 시작
    r, c, pokemon = input().split()
    r = int(r); c = int(c)
    pid = pokemon_id[pokemon]
    if not pid: # 만약 고유 번호가 저장되지 않은 포켓몬 이름이라면 (0이 나온다면)
        pokemon_id[pokemon] = pid = pokemon_unique # 고유 번호를 정해주자.
        pokemon_unique += 1
    pokemon_idxToId.append(pid) # 포켓몬의 고유 번호 저장
    for j in range(i): # 전에 입력된 포켓몬들과의 거리를 저장.
        jr, jc = pokemon_pos[j]
        d = abs(r - jr) + abs(c - jc)
        distance[i][j] = distance[j][i] = d # 양방향
    pokemon_pos.append([r, c]) # 포켓몬의 위치 저장

# 이제 외판원 순회 알고리즘을 돌리면 된다.
# dp의 크기는, 세로는 총 개수 (n + 1), 가로는 (1 << 포켓몬 종류 수).
# 포켓몬 종류당 한 마리씩만 잡으면 되기 때문이다.
dp = [[-1] * (1 << pokemon_unique) for _ in range(n + 1)]
print(dfs(0, 1 << 0))

여담

포켓몬에 관한 문제를 푸니깐 포켓몬 게임이 하고 싶다. 아르세우스 재밌을까...? 곧 포켓몬 신작 나오는 것 같던데 사볼까..?