14496번: 그대, 그머가 되어
첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 <= N <= 1,000, 1 <= M <= 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문자쌍
www.acmicpc.net
a를 b로 바꾸기 위해 필요한 최소 치환 횟수 -> a에서 b로 이동하기 위한 최단 거리
이렇게 바꾸어서 해결할 수 있습니다.
최단거리는 다익스트라를 이용합니다.
이 문제는 가중치가 주어지지 않으므로 모든 가중치는 1입니다.
입력으로 인접한 노드 번호 쌍이 주어지고 무방향 그래프입니다.
큐를 이용한 다익스트라를 사용하였고,
목적지인 b까지 도달할 수 있으면 d[des] 출력
목적지인 b까지 도달할 수 없으면 -1을 출력합니다.
다익스트라 기본 개념은 이곳에서 공부하였습니다.
23. 다익스트라(Dijkstra) 알고리즘
다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐...
blog.naver.com
[C++]
|
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 <vector>
#include <algorithm>
#include <queue>
#define INF 1000000000
using namespace std;
vector<pair<int, int> > list[1001];
int d[1001];
int N, M, start, des;
void dijkstra() {
d[start] = 0;
priority_queue<pair<int, int> > q;
q.push({ start, 0 });
while (!q.empty()) {
int x = q.top().first;
int dis = -q.top().second;
q.pop();
if (d[x] < dis) continue;
for (int i = 0; i < list[x].size(); i++) {
int next = list[x][i].first;
int nextdis = dis + list[x][i].second;
if (d[next] > nextdis) {
d[next] = nextdis;
q.push({ next, -nextdis });
}
}
}
if (d[des] == INF) cout << "-1\n";
else cout << d[des] << '\n';
}
void init() {
for (int i = 1; i <= N; i++) {
d[i] = INF;
}
}
void input() {
int u, v;
cin >> start >> des >> N >> M;
init();
while (M--) {
cin >> u >> v;
list[u].push_back({ v,1 });
list[v].push_back({ u,1 });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
dijkstra();
return 0;
}
|
cs |
[Java]
|
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
73
74
75
76
77
78
79
80
81
82
|
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static ArrayList<int[]> list[] = new ArrayList[1001];
static final int INF = 1000000000;
static int d[] = new int[1001];
static int N, M, start, des;
static void dijkstra() {
PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
q.add(new int[] { start, 0 });
d[start] = 0;
while (!q.isEmpty()) {
int now = q.peek()[0];
int dis = q.poll()[1];
if (d[now] < dis)
continue;
for (int i = 0; i < list[now].size(); i++) {
int next = list[now].get(i)[0];
int nextdis = dis + list[now].get(i)[1];
if (d[next] > nextdis) {
d[next] = nextdis;
q.add(new int[] { next, nextdis });
}
}
}
if (d[des] == INF)
System.out.println(-1);
else
System.out.println(d[des]);
}
static void init() {
for (int i = 1; i <= N; i++) {
list[i] = new ArrayList<>();
d[i] = INF;
}
}
static void input() throws Exception {
int u, v;
st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
des = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
init();
while (M-- > 0) {
st = new StringTokenizer(br.readLine());
u = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
list[u].add(new int[] { v, 1 });
list[v].add(new int[] { u, 1 });
}
}
public static void main(String[] args) throws Exception {
input();
dijkstra();
}
}
|
cs |
'algorithm > dijkstra' 카테고리의 다른 글
| boj 4485 녹색 옷 입은 애가 젤다지? (0) | 2021.03.23 |
|---|---|
| boj 18352 특정 거리의 도시 찾기 (0) | 2021.03.22 |