흙금이네 블로그

아이디어 위상 정렬로 각 도시에 도착하는 가장 늦는 시간을 구한 뒤, 도착지로부터 역으로 쉬지 않고 달리는 도로를 찾아 나간다. 풀이 입력 값들의 관계에 따라 출발 도시 리스트 parent와 도착 도시 리스트 child에 도시와 시간을 저장하고, 입력차수 리스트 degree에서 도착 도시 번호의 입력차수 값을 증가시켜 나간 후 함수 find_time과 find_road를 호출한다. 함수 find_time는 BFS로 각 도시에 도착하는 가장 늦는 시간을 구해 리스트 max_time에 저장한다. 가장 늦는 시간을 구하기 위해 방문하려는 도시의 진입차수 degree 값이 0이 되면 큐에 넣고 탐색하도록 한다. 함수 find_road는 BFS로 두 도시의 max_time 값의 차를 구해 해당 도로를 지나는 시간..