https://www.acmicpc.net/problem/2021
문제 요약
- 지하철 노선이 주어지고 최소 환승 회수를 구하기
- 역 10만, 노선 10만, 노선 길이의 합 100만
접근법
- 그래프를 리모델링하는데 많이 헤맸다
- 처음에는 노선과 노선을 연결하는 간선을 구하려고 했음
- 노선끼리 연결한 그래프 생성 후 dijkstra
- 노선 -> 포함된 역 -> 역에 연결된 노선 을 생각하면 N^2 복잡도 발생
- N이 10만이면 바로 정답을 구하겠지만 5만씩 애매하게 분포되어있으면 힘듬
- 역 -> 노선 -> 역으로 가면 좋을텐데 아이디어 도출이 힘들었음
- 어떤 역에서 한번에 갈 수 있는 곳을 다 방문하고, 다음번에도 반복하고 하면서 환승 회수를 증가시키는 아이디어로 접근했음
- 역의 방문처리와 노선의 방문 처리를 둘다 했음
- 역 -> 역이 포함된 노선 -> 노선을 방문 안했으면 -> 노선에 포함된 역 -> 역을 방문 안했으면 -> q에 추가
- 역과 연결된 모든 역을 탐색해서 q에 추가하게 됨 => 이때 추가가 안된 역은 바로 못가는 역임 => 다음번 언젠가의 탐색에서 방문을 할 것임
- 최초 역에서 바로 갈 수 있는 역에도 + 1이 되기때문에 별도 처리함
- 특정 점에 대해서 1단계만 전체로 확산하고, 그다음에는 또 확산하고.. 이런 BFS 접근임
- 어짜피 모든 역 + 모든 노선만 방문하기때문에 시간복잡도도 안전할 것임. 엣지도 100만이고
다른 접근법
- 정리가 잘 안되어서 다른 분들 아이디어를 검색해봄
- 역 + 노선(+10만)으로 노드 구성
- 역 - 노선만 간선으로 연결
- 역 -> 노선 : 방문 + 1 ==> 어쨌든 그 점을 통해서 노선간 이동이 발생한 것이기때문에 환승이 된것임
- 노선 -> 역 : 방문 + 0
newbieski