'역추적' 태그의 글 목록

얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다. 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요? 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요. 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 ..