Pokemon Go Go
시간 제한5초메모리 제한512 MB
원점에서 출발해 그대로 돌아오는 최단 경로를 구합니다. 최대 20개 포켓스톱마다 좌표와 포켓몬 이름이 주어질 때, 서로 다른 포켓몬을 모두 한 번씩 잡는 경로의 최소 이동 거리를 구합니다.
문제
Always Catch your Mon, Inc.(ACM)는 Pokémon Go Go라는 새 제품을 만들려고 한다. 사용자는 이 애플리케이션을 구매해 Pokémon Go를 플레이할 때 도움을 받을 수 있다. 이 소프트웨어는 현재 위치 근처의 포켓스톱 위치와 각 포켓스톱에서 발견할 수 있는 포켓몬 목록을 가져온다. 그런 다음 모든 고유 포켓몬을 잡고 출발점으로 돌아오는 최단 경로를 계산한다.
이 프로그램은 이동이 남북 및 동서 방향으로만 제한된 도시에 사용자가 있다고 가정한다. 또한 모든 포켓스톱이 두 도로의 교차점에 있다고 가정한다.
예를 들어, 애플리케이션이 근처에서 다섯 개의 포켓스톱을 찾았다고 하자. 각 스톱의 위치는 두 정수 (r,c)로 나타내며, r은 출발 위치에서 북쪽으로 몇 블록인지, c는 서쪽으로 몇 블록인지를 뜻한다. 다섯 포켓스톱의 위치가 (5, 9), (20, 20), (1, 1), (1, 8), (2, 8)이고 이 스톱에서 발견되는 포켓몬의 이름이 각각 Evevee, Flareon, Flareon, Jolteon, Umbreon이라고 하자. 같은 포켓몬을 어느 쪽에서든 잡을 수 있으므로 두 번째와 세 번째 스톱을 모두 방문할 필요는 없다. 최선의 경로는 첫 번째, 다섯 번째, 네 번째, 세 번째 스톱을 그 순서로 방문하는 것이며 총 거리는 28블록이다. 그 이유는 다음과 같다.
- (0, 0)에서 (5, 9)까지의 거리는 14이다.
- (5, 9)에서 (2, 8)까지의 거리는 4이다.
- (2, 8)에서 (1, 8)까지의 거리는 1이다.
- (1, 8)에서 (1, 1)까지의 거리는 7이다.
- (1, 1)에서 (0, 0)까지의 거리는 2이다.
입력
입력은 단일 테스트 케이스로 이루어진다. 테스트 케이스는 정수 n으로 시작하며, 0 < n ≤ 20이고 이는 고려할 포켓스톱의 수이다. 다음 n개의 각 줄은 포켓스톱의 위치와 그곳에서 발견할 수 있는 포켓몬의 이름을 지정한다. 위치는 공백 하나로 구분된 두 정수 r과 c로 지정되며, −100 ≤ r, c ≤ 100이다. 정수 r과 c는 스톱이 출발점에서 북쪽으로 r블록, 동쪽으로 c블록 떨어져 있음을 뜻한다. 위치 뒤에는 공백 하나가 오고, 그곳에서 잡을 수 있는 포켓몬의 이름을 나타내는 문자열 p가 온다. 이름은 1자 이상 25자 이하이며 알파벳 대소문자(a–z, A–Z)만 쓴다. 고유 포켓몬의 수는 항상 15 이하이다. 한 포켓스톱에 여러 포켓몬이 있을 수 있으며 각각 별도의 줄에 나열된다.
출력
모든 고유 포켓몬을 잡는 데 필요한 최단 거리를 블록 단위로 출력한다.