0번을 이길자가 없다
Dijkstra
다익스트라
다익스트라 응용
플루이드 워셜
Dijkstra 사용법
-
최신데이터가 맞는가?
-
큐등록
-
result배열첨에 값이 크기 때문에 old data이다.
다익스트라 연습
0번에서 5번 갈수있나??
다익스트라, bfs
- 가중치가 없는경우 - bfs
- 가중치 있는 경우 - 다익스트라
이거헷갈려,,,
최신데이터가 맞는가?
자꾸 에러난이유
price값 갱신하는거 헷갈렸음!!!!
int price값!
[다익스트라 버전]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
int n;
int price;
};
vector<vector<Node>>alist(6);
const int MAXI = 21e8;
priority_queue<Node>q;
bool operator<(Node v, Node t) {
return t.price < v.price;
}
int result[6] = { 0,MAXI,MAXI,MAXI,MAXI,MAXI};
int main() {
alist[0] = { {1,1},{2,1},{3,1} };
alist[1] = { {2,1} };
alist[2] = { {3,1} };
alist[4] = { {3,1},{5,1} };
alist[5] = { {0,1} };
q.push({ 0,0 });
while (!q.empty()) {
Node now = q.top();
q.pop();
//1. 최신 데이터인지 확인한다.
if (result[now.n] < now.price)continue;
//2. 큐 등록
for (int i = 0; i < alist[now.n].size(); i++) {
Node next = alist[now.n][i];
int price = now.price + next.price;
if (result[next.n] > price) {
result[next.n] = price;
q.push({ next.n,price });
}
}
}
for (int i = 0; i < 6; i++) {
cout << result[i] << " ";
}
return 0;
}
그래서 배열에 21억값이 있으면 못가는고다.
[bfs 버전]
bfs, dfs 와 다익스트라와의 차이점
가중치값없음, a->b bfs
가중치값 있음, a->b 다익스트라
다익스트라 응용
문제 연습
[문제]
1) 시작 지점
2)
최소 피로도,,
값을 계속 업데이트 시켜주면서, 정렬을 해주는건가? 흠냐
맨날 방향벡터할때 좌표값 실수함! 조심하기!
int dy =now.y+ direct[t][0];
int dx =now.x+ direct[t][1];
[행렬이용 다익스트라]
#include <iostream>
#include <queue>
using namespace std;
int direct[4][2] = { -1,0,1,0,0,1,0,-1 };
int map[4][4] = {
2,2,1,1,
3,1,30,1,
0,20,50,2,
2,5,3,0
};
struct Node {
int y, x;
int price;
};
bool operator<(Node v, Node t) {
return t.price < v.price;
}
priority_queue<Node>q;
const int MAXI = 21e8;
int result[4][4];
int main() {
for (int y = 0; y < 4; y++) {
for (int x = 0; x < 4; x++) {
result[y][x] = MAXI;
}
}
result[1][1] = 1;
q.push({ 1,1,1 });
while (!q.empty()) {
//1. 최신 데이터인지 확인한다.
Node now = q.top();
q.pop();
if (result[now.y][now.x] < now.price)continue;
for (int t = 0; t < 4; t++) {
int dy =now.y+ direct[t][0];
int dx =now.x+ direct[t][1];
if (dy < 0 || dx < 0 || dy >= 4 || dx >= 4)continue;
int total = now.price + map[dy][dx];
if (total < result[dy][dx]) {
result[dy][dx] = total;
q.push({ dy,dx,total });
}
}
}
return 0;
}
경로의 최댓값만 유지하면 된다.
가장 비싼금액만 정해준다.
원래 합을 적어줬는데, 이거는 비싼금액을 유지시켜 준다.
[아이디어]
1. 큐에는 더 큰값을 리턴 시켜준다.
2. result 배열에는 더 작은값으로 갱신 시켜준다.
경로중의 최대값구하기
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX= 21e5;
int result[5];
struct Node {
int n;
int price;
};
vector<vector<Node>>alist(5);
bool operator<(Node v, Node t) {
return t.price<v.price;
}
priority_queue<Node>q;
int main() {
for (int i = 0; i < 5; i++) {
result[i] = MAX;
}
result[0] = 0;
alist[0] = { {1,8},{3,10},{4,4} };
alist[1] = { {1,2} };
alist[2] = { {3,2} };
alist[4] = { {2,3},{3,5} };
q.push({ 0,0 });
while (!q.empty()) {
Node now = q.top();
q.pop();
//1. 최신 데이터인가?
if (result[now.n] < now.price)continue;
for (int i = 0; i < alist[now.n].size(); i++) {
Node next = alist[now.n][i];
// 비교한다. next.price vs now.price -> 더 큰거 선택
int bigNum = max(next.price, now.price);
if (result[next.n] > bigNum) {
result[next.n] = bigNum;
q.push({ next.n,bigNum });
}
}
}
cout << result[3];
return 0;
}
[출력]
4
다익스트라?
한 지점에서 모든 경로로 가는 최솟값 을 구하는것
플루이드 워셜
[문제1]
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int M= 21e5;
int map[4][4] = {
0,3,4,2,
M,0,10,1,
M,M,0,M,
M,2,6,0
};
int main() {
//1.경유할곳v
//2. 출발지점a
//3. 도착지점b
//못가는 지점은 생략
for (int v = 0; v < 4; v++) {
for (int a = 0; a < 4; a++) {
for (int b = 0; b < 4; b++) {
if (map[a][b] > map[a][v] + map[v][b]) {
map[a][b] = map[a][v] + map[v][b];
}
}
}
}
//만약에 경유 하는것이 나으면, 경유를 한다.
return 0;
}
[문제2]
computer_log