[codingame 번역] TAN Network

Practice Pathfinding and Graphs with the exercise "TAN Network"

🚩목표

프랑스에 위치한 루아르-아틀랑티크 지역의 행정부는 많은 양의 대중교통 정보를 대중에게 공개하기로 결정했다. 이 지역을 담당하는 대중교통 회사의 이름은 TAN입니다.
이 정보의 한 부분은 TAN 정류장, 시간표 및 노선 목록입니다. 이 지역에서는 TAN 사용자에게 TAN 네트워크를 사용하는 두 정류장 사이의 최단 경로를 계산할 수 있는 도구를 제공하려고 합니다.

 

✅규칙

프로그램에 필요한 입력 데이터는 ASCII 텍스트 형식으로 제공됩니다.

 - 여행의 시작점인 정류장.
 - 여행의 종착점인 정류장.
 - 모든 정류장 목록
 - 정류장 사이의 노선


모든 정류장 리스트:

  각각의 라인마다 다음의 필드를 포함합니다.

 - 정류장 고유의 식별자
 - 따옴표( " )로 된 정류장의 풀네임
 - 정류장에 대한 설명 (사용되지 않음)
 - 정류장의 위도 (도수법)
 - 정류장의 경도 (도수법)
 - 영역에 대한 식별자 (사용되지 않음)
 - 정류장의 url (사용되지 않음)
 - 정류장 유형
 - 엄마역 (사용되지 않음)
 위 필드는 컴마( , ) 로 구분됩니다.

  <예시>
  StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,

정류장 사이의 경로:
  리스트의 각 라인은 정류장 사이의 노선입니다. 노선마다 두 정류장의 식별코드를 각각 포함합니다.

  각 노선은 첫번째 정류장에서 두 번째 정류장으로 가는 식별코드를 나타냅니다. (편도)
  만약 두 정거장 사이을 왕복가능한 노선을 표현한다면 다음과 같이 나타냅니다.
  A B
  B A
  <예시>
  StopArea:LAIL StopArea:GALH
  StopArea:GALH StopArea:LAIL


거리계산:
  두 점 A와 B 사이의 거리는 다음 공식을 사용하여 계산됩니다.

노트: 위도와 경도는 라디안으로 표시됩니다. 6371은 지구의 반지름(km)에 해당합니다.

 

  프로그램은 가장 짧은 경로의 정류장의 전체 이름 목록을 표시하여야 합니다.
  출발지와 목적지 사이에 가능한 경로가 없을 경우 프로그램에 IMPOSABLE을 출력하면 됩니다.

🎮입력

라인 1: 여행의 시작점인 정류장의 식별코드입니다.

라인 2: 여행의 종착점인 정류장의 식별코드 입니다.

라인 3:  숫자 N, TAN네트워크에 있는 정류장의 수입니다.

다음 N개 라인: 각 정류장에 대한 설명입니다.

다음 라인 :숫자 M, TAN네트워크에 있는 노선의 수 입니다.

다음 M개 라인: 각 노선에 대한 설명입니다.

💻출력

시작점에서 종착점까지의 최단 경로의 있는 모든 정류장의 풀네임(한 줄당 한 이름)을 출력하세요. 이 때,  이름은 따옴표( " ) 사이에 있으면 안 됩니다.
시작점과 끝점 사이의 경로를 찾을 수 없는 경우 IMPOSABLE을 출력하세요.

제약 조건
0 < N < 10000
0 < M < 10000

입출력 예시

Input

StopArea:ABDU
StopArea:ABLA
3
StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,
StopArea:ABLA,"Avenue Blanche",,47.22973509,-1.58937990,,,1,
StopArea:ACHA,"Angle Chaillou",,47.26979248,-1.57206627,,,1,
2
StopArea:ABDU StopArea:ABLA
StopArea:ABLA StopArea:ACHA

Output

Abel Durand
Avenue Blanche

 

 

The Goal

The administration of the Loire-Atlantique region, located in France, has decided to open up a large amount of public transportation information to the public. The public transport company in charge for this area is named TAN.

One part of this information is the list of TAN stops, timetables and routes. The region wants to provide TAN users with a tool which will allow them to calculate the shortest route between two stops using the TAN network.

 

 

 Rules

The input data required for your program is provided in an ASCII text format:

• The stop which is the starting point of the journey
• The stop which is the final point of the journey
• The list of all the stops
• The routes between the stops

 

List of all the stops:

A series of lines representing the stops (one stop per line) and which contains the following fields:

• The unique identifier of the stop
• The full name of the stop, between quote marks"
• The description of the stop (not used)
• The latitude of the stop (in degrees)
• The longitude of the stop (in degrees)
• The identifier of the zone (not used)
• The url of the stop (not used)
• The type of stop
• The mother station (not used)

These fields are separated by a comma ,

 

Example:

StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,

 

The routes between stops:

A list of lines representing the routes between the stops (one route per line). Each line contains two stop identifiers separated by a white space. ​

Each line represents a one-directional route running from the first identifier to the second. If two stops A and B are reciprocally accessible, then there will be two lines to represent this route:
A B
B A

Example:

StopArea:LAIL StopArea:GALH
StopArea:GALH StopArea:LAIL

DISTANCE

The distance d between two points A and B will be calculated using the following formula:

​

Note: the latitudes and longitudes are expressed in radians. 6371 corresponds to the radius of the earth in km.

The program will display the list of the full names of the stops along which the shortest route passes. If there is no possible route between the starting and final stops, the program will display IMPOSSIBLE.

Game Input

 

Input

Line 1: the identifier of the stop which is the starting point of the journey

Line 2: the identifier of the stop which is the final point of the journey

Line 3: the number N of stops in the TAN network

N following lines: on each line a stop as described above

Following line: the number M of routes in the TAN network

M following lines: on each line a route as described above

 

Output

The list of the stops with their full names (one name per line) along which the shortest route passes from the start to the end of the journey (start and end included) The names must not be between quotes ".
If it is not possible to find a route between the start and end points, the program should display IMPOSSIBLE.

 

Constraints

0 < N < 10000
0 < M < 10000

 

Example

Input

StopArea:ABDU
StopArea:ABLA
3
StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,
StopArea:ABLA,"Avenue Blanche",,47.22973509,-1.58937990,,,1,
StopArea:ACHA,"Angle Chaillou",,47.26979248,-1.57206627,,,1,
2
StopArea:ABDU StopArea:ABLA
StopArea:ABLA StopArea:ACHA

Output

Abel Durand
Avenue Blanche​

 

<역자 후기> (블로그 주인)

쉬운 것 같으면서도 의외로 삑사리가 난다. 왠지 디버그에 걸리는 시간이 아까운 것 같은 문제...

import sys

import math

 

# Auto-generated code below aims at helping you parse

# the standard input according to the problem statement.

 

start_point = input().split(":")[1]

end_point = input().split(":")[1]

n = int(input())

print(start_point,end_point)

info = {}

for i in range(n):

    stop_name,fname, _ , lat, lon , *_  = input().split(":")[1].split(",")

    info[stop_name] = [fname.replace("\"",""), float(lat), float(lon)]

 

m = int(input())

con = {}

for i in range(m):

    route = input().replace('StopArea:','').split()

    if route[0] not in con : con[route[0]]= {}

    fname , lat, lon = info[route[0]]

    fname2 , lat2, lon2  = info[route[1]]

    x = (lon2-lon) * math.cos( (lat+lat2)/2 *math.pi / 180)

    y = (lat2-lat)

    d = abs(x + 1j*y)*6371

    con[route[0]][route[1]]=d

 

node = {start_point:0}

pstop = {start_point:"?"}

goto = set()

for stop in info:

    if stop == start_point: continue

    node[stop] = stop in con[start_point] and con[start_point][stop] or 999999

    goto.add(stop)

    pstop[stop] = start_point

 

while goto:

    stop = min(goto,key=lambda x: node[x])

    goto.remove(stop)

    if stop not in con : continue

    for nx in con[stop]:

        if node[nx] <= node[stop] + con[stop][nx] : continue

        node[nx] = node[stop] + con[stop][nx]

        pstop[nx] = stop

       

idx = end_point

rs = []

while idx in pstop:

    rs=[info[idx][0]]+rs

    idx = pstop[idx]

 

print( node[end_point] >= 999999 and "IMPOSSIBLE" or "\n".join(rs))