반응형
https://www.acmicpc.net/problem/5214
5214번: 환승
첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어
www.acmicpc.net
[ 문제풀이 ]
1. visited [ N + K ] 배열을 만들어서 방문 여부를 저장합니다.
2. 하이퍼링크를 정점으로 두고, 하이퍼링크를 입력받을 때 다음과 같이 간선을 설정해 줍니다.
list [ N + i ].push_back(station)
list [station].push_back(N + i)
3. 즉, 역과 연결된 정점은 하이퍼링크이고, 하이퍼링크와 연결된 정점은 역으로 설정해 줍니다.
4. 만약 현재 정점이 N보다 크다면 역이 아니고 하이퍼링크이므로, 현재 방문한 역의 개수를 queue에 넣어주고, N보다 작거나 같다면 역에 방문한 것이므로, 현재 방문한 역의 개수에 +1을 해주어 queue에 넣어줍니다.
5. 현재 역이 N번 역이라면 cnt를 출력해 줍니다.
6. 방문할 수 없다면 -1을 출력해 줍니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #include<iostream> #include<queue> #include<vector> using namespace std; int N, K, M; vector<int> list[101001]; int visited[101001]; struct node { int cur; int cnt; }; int main() { scanf("%d %d %d", &N, &K, &M); for (int i = 1; i <= M; i++) { for (int j = 0; j < K; j++) { int station; scanf("%d", &station); list[station].push_back(N + i); list[N + i].push_back(station); } } queue<node> q; q.push({ 1,1 }); visited[1] = 1; while (!q.empty()) { const int cur = q.front().cur; const int cnt = q.front().cnt; q.pop(); if (cur == N) { printf("%d", cnt); return 0; } for (auto next : list[cur]) { if (visited[next] != 1) { visited[next] = 1; if (next > N) { q.push({ next, cnt }); } else { q.push({ next,cnt + 1 }); } } } } printf("-1"); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1261번 - 알고스팟 (C++) (0) | 2023.02.03 |
|---|---|
| [ 백준 ] 10423번 - 전기가 부족 (C++) (0) | 2023.02.02 |
| [ 백준 ] 1584번 - 게임 (C++) (0) | 2023.01.31 |
| [ 백준 ] 1175번 - 배달 (C++) (0) | 2023.01.30 |
| [ 백준 ] 13418번 - 학교 탐방하기 (C++) (0) | 2023.01.29 |