📝 문제 정보#
🧐 관찰 및 접근#
- 나이브하게 생각해볼까?
- 인접 리스트로 간선을 저장한다고 생각하면, $M\binom{K}{2} \approx MK^2$ 개의 정보가 저장된다.
- 그러면 BFS의 시간복잡도는 $O(V+E)$ 니까 조금 곤란한데…
- 잘 생각해보면, (1, 2, 3, 4), (2, 3, 4, 5) 하이퍼튜브가 있다고 가정하면, 겹치는 정보가 너무나도 많다!
- 첫 하이퍼튜브를 타고 2, 3, 4번 역에 1회만에 도착했다면, 두번째 하이퍼튜브에서 2, 3, 4번이 서로를 움직일 필요가 없다.
- 하이퍼튜브는 최대 1000개 존재한다.
- 또한 한 역은 최대 1000개의 하이퍼튜브에 속한다.
- 하이퍼튜브만 따로 정리해서, 그 안에서 움직이면 되지 않을까?
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> K >> M;
rep(i, 0, M){
rep(j, 0, K){
int x; cin >> x;
inhyper[x].push_back(i);
hypertube[i].push_back(x);
}
}
rep(i, 1, N+1) dist[i] = -1;
dist[1] = 1;
queue<int> q;
q.push(1);
while(!q.empty()){
int cur = q.front(); q.pop();
if(cur == N) break;
for(int htube : inhyper[cur]){
for(int nxt : hypertube[htube]){
if(dist[nxt] == -1){
dist[nxt] = dist[cur] + 1;
q.push(nxt);
}
}
hypertube[htube].clear(); // 이미 방문한 하이퍼튜브는 볼일이 없다
}
}
cout << dist[N] << '\n';
}