18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
bfs와 다익스트라 두 가지방법 모두 사용하였습니다.
이 문제는 방향그래프이므로 u v 로 입력이 오면 u -> v로 받아야합니다.
먼저 다익스트라 알고리즘 방법으로는 가중치가 주어지지 않았기때문에 1로 두고 다익스트라 알고리즘을 이용하여 start에서 각 노드까지 최단거리를 다 구해줍니다.
최단거리가 K인 노드가 있으면 오름차순으로 출력해주고, 없으면 -1을 출력합니다.
bfs 방법으로는 start에서부터 시작하여 bfs를 K번 진행합니다.
bfs로 탐색하면서 각 노드까지의 거리를 갱신해줍니다.
최단거리가 K인 노드가 있으면 오름차순으로 출력해주고, 없으면 -1을 출력합니다.
다익스트라는 모든 정점까지의 최단거리를 다 구해주기 때문에 시간 상으로는 bfs가 훨씬 효율적입니다.
[dijkstra]
|
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <iostream>
#include <queue>
#include <vector>
#define INF 1000000000
using namespace std;
vector<pair<int, int> > list[300001];
int d[300001];
int N, M, K, start;
void solve() {
bool chk = false;
for (int i = 1; i <= N; i++) {
if (d[i] == K) {
chk = true;
cout << i << '\n';
}
}
if (!chk) cout << "-1\n";
}
void dijkstra() {
d[start] = 0;
priority_queue<pair<int, int> > q;
q.push({ start, 0 });
while (!q.empty()) {
int now = q.top().first;
int dis = -q.top().second;
q.pop();
if (d[now] < dis) continue;
for (int i = 0; i < list[now].size(); i++) {
int next = list[now][i].first;
int nextdis = dis + list[now][i].second;
if (d[next] > nextdis) {
d[next] = nextdis;
q.push({ next, -nextdis });
}
}
}
}
void init() {
for (int i = 1; i <= N; i++) {
d[i] = INF;
}
}
void input() {
int u, v;
cin >> N >> M >> K >> start;
init();
while (M--) {
cin >> u >> v;
list[u].push_back({ v,1 });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
dijkstra();
solve();
return 0;
}
|
cs |
[bfs]
|
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
58
59
60
61
62
63
|
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
vector<int> list[300001];
queue<int> q;
int d[300001];
int N, M, K, start;
void solve() {
bool chk = false;
for (int i = 1; i <= N; i++) {
if (d[i] == K) {
chk = true;
cout << i << '\n';
}
}
if (!chk) cout << "-1\n";
}
void bfs() {
q.push(start);
d[start] = 0;
for (int t = 1; t <= K; t++) {
int qsize = q.size();
while (qsize--) {
int x = q.front();
q.pop();
for (int i = 0; i < list[x].size(); i++) {
int next = list[x][i];
if (d[next] != -1) continue;
q.push(next);
d[next] = t;
}
}
}
}
void input() {
int u, v;
cin >> N >> M >> K >> start;
while (M--) {
cin >> u >> v;
list[u].push_back(v);
}
memset(d, -1, sizeof(d));
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
bfs();
solve();
return 0;
}
|
cs |
'algorithm > dijkstra' 카테고리의 다른 글
| boj 4485 녹색 옷 입은 애가 젤다지? (0) | 2021.03.23 |
|---|---|
| boj 14496 그대, 그머가 되어 (0) | 2021.03.22 |