1. 그래프 표현 방법
● 인접 행렬을 이용한 그래프 구현
< 그래프를 어떻게 인접행렬로 구현할 수 있을까? >
→ 위의 그림처럼 정점 0과 정점 1이 연결되어 있다면 행렬 상의 (1,0)의 값을 1로 바꾸어 연결
되었음을 나타낸다.
만약 두 정점과 연결이 없다면 행렬 상의 값을 0으로 설정해 연결이 안 되어있음을
나타낸다.
행렬이 대칭을 이루면 무방향 그래프이다. 대칭 여부에 따라 방향/무방향 그래프를 구분
할 수 있다.
< c++로 인접행렬 그래프 구현하기 >
→ 인접행렬 그래프를 구현한 class를 선언
인접행렬로 사용할 행렬을 선언
그래프의 간선 정보를 입력 또는 반환할 수 있는 함수를 각각 선언
그래프의 정점 정보를 입력 또는 반환할 수 있는 함수를 각각 선언
저장한 간선, 정점 정보들을 display 할 수 있는 함수를 선언
→ main 함수를 통해 인접행렬 그래프 class에 객체 생성
간선 정보를 모두 입력받아 인접행렬 그래프에 insert
class AdjMatGraph {
protected:
int size;
char vertices[MAX_VTXS];
int adj[MAX_VTXS][MAX_VTXS];
public:
AdjMatGraph() { reset(); }
char getVertex(int i) { return vertices[i]; }
int getEdge(int i, int j) { return adj[i][j]; }
void setEdge(int i, int j, int val) { adj[i][j] = val; }
bool isEmpty() { return size == 0; }
bool isFull() { return size >= MAX_VTXS; }
void reset() {
size = 0;
for (int i = 0; i < MAX_VTXS; ++i)
for (int j = 0; j < MAX_VTXS; ++j)
setEdge(i, j, 0);
}
void insertVertex(char name) {
if (!isFull()) vertices[size++] = name;
else cout << "ERROR : 그래프 정점 개수 초과" << endl;
}
void insertEdge(int u, int v) {
setEdge(u, v, 1);
setEdge(v, u, 1);
}
void display() {
cout << size << endl;
for (int i = 0; i < size; ++i) {
cout << getVertex(i) << " ";
for (int j = 0; j < size; ++j)
cout << getEdge(i, j) << " ";
cout << endl;
}
}
};
int main()
{
AdjMatGraph g;
for (int i = 0; i < 4; i++)
g.insertVertex('A' + i);
g.insertEdge(0, 1);
g.insertEdge(0, 3);
g.insertEdge(1, 2);
g.insertEdge(1, 3);
g.insertEdge(2, 3);
cout << "인접 행렬로 표현한 그래프" << endl;
g.display();
}
● 인접 리스트를 이용한 그래프 구현
< 그래프를 어떻게 인접 리스트로 구현할 수 있을까? >
→ 위의 그림처럼 정점 A와 정점 B가 연결되어 있다면 노드 A의 포인터 변수로 노드 B를
가르킴으로써 두 노드가 그래프 상에서 연결되어 있음을 표현한다.
위의 그림을 더 자세히 보자면
정점 A와 연결된 정점들은 B, C, D
정점 B와 연결된 정점들은 A, C
정점 C와 연결된 정점들은 A, B, D
정점 D와 연결된 정점들은 A, C 임을 나타낸다.
노드를 사용해 연결된 부분을 가리키도록 하기 때문에 방향그래프로도 구현이 가능하다.
< c++로 인접리스트 그래프 구현하기 >
→ 인접리스트 그래프를 구현을 위해 필요한 Node class를 선언
정점 정보를 넣을 char 변수 선언
다음 노드를 가리킬 포인터 변수 선언
포인터 변수를 설정하도록 하는 함수, 어떤 노드를 가리키고 있는 지 그 값을 반환하도록
하는 함수를 선언
→ 인접리스트 그래프를 구현한 class를 선언
정점 삽입 연산을 하는 함수를 선언
간선 삽입 연산을 하는 함수를 선언, 이 함수가 실행되면 새로운 노드를 만들어 두 정점을
연결
현재 그래프가 어떻게 연결되어 있는 지 보여주는 display 함수를 선언
→ main 함수를 통해 인접리스트 그래프 class에 객체 생성하고 실행
정점과 간선 정보를 인접리스트 그래프에 insert
class Node {
protected:
char id; // 정점의 id
Node* link; // 다음 노드의 포인터
public:
Node(int i, Node* l = NULL) : id(i), link(l) { }
~Node() {
if (link != NULL) delete link;
}
int getID() { return id; }
Node* getLink() { return link; }
void setLink(Node* l) { link = l; }
};
class AdjListGraph {
protected:
int size; // 정점의 개수
char vertices[MAX_VTXS]; // 정점 정보
Node* adj[MAX_VTXS]; // 각 정점의 인접 리스트
public:
AdjListGraph() : size(0) { }
~AdjListGraph() { reset(); }
void reset(void) {
for (int i = 0; i < size; i++)
if (adj[i] != NULL) delete adj[i];
size = 0;
}
void insertVertex(char val) { // 정점 삽입 연산
if (!isFull()) {
vertices[size] = val;
adj[size++] = NULL;
}
else cout << "ERROR : 그래프 정점 개수 초과" << endl;
}
void insertEdge(int u, int v) { // 간선 삽입 연산
adj[u] = new Node(v, adj[u]); // 인접 리스트에 추가
adj[v] = new Node(u, adj[v]); // 방향 그래프 ==> 주석 처리함
}
void display() {
cout << "Number of vertex : " << size << endl;
for (int i = 0; i < size; i++) { // 각 행의 정보 출력
cout << getVertex(i) << " ";
for (Node* v = adj[i]; v != NULL; v = v->getLink())
cout << getVertex(v->getID()) << " ";
cout << endl;
}
}
Node* adjacent(int v) { return adj[v]; }
bool isEmpty() { return size == 0; }
bool isFull() { return size >= MAX_VTXS; }
char getVertex(int i) { return vertices[i]; }
};
int main()
{
AdjListGraph LG; // 새로운 그래프 객체 생성
for( int i=0 ; i<4 ; i++ )
LG.insertVertex('A'+i); // 정점 삽입: 'A' 'B', ...
LG.insertEdge(0, 1); //A,B // 간선 삽입
LG.insertEdge(0, 3); //A,D
LG.insertEdge(1, 2); //B,C
LG.insertEdge(1, 3); //B,D
LG.insertEdge(2, 3); //C,D
cout << "연결 리스트로 표현한 그래프" << endl;
LG.display();
}
2. 다익스트라 알고리즘
● 다익스트라 알고리즘 설명
→ 다익스트라 알고리즘은 BFS를 사용해 최단 경로를 찾는 "최단 경로 탐색 알고리즘" 중
하나이다.
< BFS >
→ 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는
순회 방법
→ 위의 그림을 자세히 설명해 보겠다.
정점 A로 시작한다.
A를 탐색하기 위해 큐에 넣고 A는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
A와 연결된 B, C를 큐에 넣어 두어 다음 순서로 탐색하도록 한다.
B와 C는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
A의 탐색이 끝났으므로 큐에서 A를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. B이다.
B와 연결된 A, D를 큐에 넣는다. A는 이미 '방문했음'으로 표시되어 있으므로 D만 큐에
넣는다.
D는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
B의 탐색이 끝났으므로 큐에서 B를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. C이다.
C와 연결된 A, D, E를 큐에 넣는다. A, D는 이미 '방문했음'으로 표시되어 있으므로
E만 큐에 넣는다.
E는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
C의 탐색이 끝났으므로 큐에서 C를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. D이다.
D와 연결된 B, C, F를 큐에 넣는다. B, C는 이미 '방문했음'으로 표시되어 있으므로
F만 큐에 넣는다.
F는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
D의 탐색이 끝났으므로 큐에서 D를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. E이다.
E와 연결된 C, G, H를 큐에 넣는다. C는 이미 '방문했음'으로 표시되어 있으므로
G, H만 큐에 넣는다.
G, H는 '방문했음'으로 표시해 다시 탐색하지 않도록 한다.
E의 탐색이 끝났으므로 큐에서 E를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. F이다.
F와 연결된 D를 큐에 넣는다. D는 이미 '방문했음'으로 표시되어 있다.
(더 이상 탐색을 위해 큐에 추가할 정점이 없다)
F의 탐색이 끝났으므로 큐에서 F를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. G이다.
G와 연결된 E, H를 큐에 넣는다. E, H는 이미 '방문했음'으로 표시되어 있다.
(더 이상 탐색을 위해 큐에 추가할 정점이 없다)
G의 탐색이 끝났으므로 큐에서 G를 빼낸다.
큐에서 다음으로 탐색할 정점을 빼낸다. H이다.
H와 연결된 G를 큐에 넣는다. G는 이미 '방문했음'으로 표시되어 있다.
(더 이상 탐색을 위해 큐에 추가할 정점이 없다)
H의 탐색이 끝났으므로 큐에서 H를 빼낸다.
"ABCDEFGH" 순서로 모든 탐색이 완료되었다.
< 다익스트라 알고리즘 >
→ 다익스트라 알고리즘은 위와 같은 BFS의 원리를 이용해 두 정점 사이의
최단 경로를 탐색하는 알고리즘이다.
→ 다익스트라 알고리즘은 시작노드와 연결되어 있는 노드들을 큐에 저장한다.
(큐에 저장할 때는 해당 노드를 '방문했음'으로 바꿔주어 다시 방문하지 않도록 한다.)
연결된 노드들을 둘러볼 때 시작노드로부터 현재 노드까지의 가중치의 값들을 다 더해
가장 작은 경우의 노드를 최단 경로 배열에 저장한다.
(새롭게 최단 경로 배열을 만들어 시작노드로부터 가중치가 가장 작은 노드를 저장하는
과정만 추가되고 기본 탐색과정은 BFS와 같다.)
원하는 목적지 정점에 도착할 때까지 탐색을 진행한 후 종료한다.
● 다익스트라 알고리즘 코드 구현
→ AdjMatGraph 클래스
가중치 그래프를 표현하는 인접행렬을 구현한 클래스
→ WGraph 클래스
가중치를 표현하는 클래스
인접행렬 클래스에 가중치 정보도 함께 저장하도록 두 정점과 가중치 정보를 입력받아
인접행렬에 1 또는 0의 값이 아닌 가중치 값을 대입해 저장해둠
정점 정보, 가중치 정보를 입력받는 load 함수도 있음
→ WGraphDijkstra 클래스
다익스트라 알고리즘의 최단 경로 탐색 기능이 추가된 그래프
chooseVertex() 함수는 가장 비용이 적은 미방문 정점을 반환하는 함수
printDistance() 함수는 모든 정점들의 dist[] 값을 출력해주는 함수
PrintPath(int start, int end) 함수는 최단 경로를 print 해주는 함수
ShortestPath(int start) 함수는 다익스트라 최단 경로 알고리즘이 구현된 함수로,
최단 경로를 찾아주는 함수
→ main 함수
main 함수를 통해 다익스트라 클래스에 객체를 생성한 후 최단경로 탐색 함수를 실행해
원하는 코드를 작동하도록 함
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_VTXS 100
#define INF 9999 // INF이면 간선없음
// 가중치 그래프를 표현하는 클래스
class AdjMatGraph {
protected:
int size;
char vertices[MAX_VTXS];
int adj[MAX_VTXS][MAX_VTXS];
public:
AdjMatGraph() { reset(); }
char getVertex(int i) { return vertices[i]; }
int getEdge(int i, int j) { return adj[i][j]; }
void setEdge(int i, int j, int val) { adj[i][j] = val; }
bool isEmpty() { return size == 0; }
bool isFull() { return size >= MAX_VTXS; }
void reset() {
size = 0;
for (int i = 0; i < MAX_VTXS; ++i)
for (int j = 0; j < MAX_VTXS; ++j)
setEdge(i, j, 0);
}
void insertVertex(char name) {
if (!isFull()) vertices[size++] = name;
else cout << "ERROR : 그래프 정점 개수 초과" << endl;
}
void insertEdge(int u, int v) {
setEdge(u, v, 1);
setEdge(v, u, 1);
}
void display() {
cout << size << endl;
for (int i = 0; i < size; ++i) {
cout << getVertex(i) << " ";
for (int j = 0; j < size; ++j)
cout << getEdge(i, j) << "\t";
cout << endl;
}
}
};
// 가중치 그래프를 표현하는 클래스
class WGraph : public AdjMatGraph {
public:
void insertEdge(int u, int v, int weight) {
if (weight > INF) weight = INF;
setEdge(u, v, weight);
}
bool hasEdge(int i, int j) { return (getEdge(i, j) < INF); }
void load(string filename) {
ifstream fp(filename);
if (fp.is_open()) {
int n, val;
fp >> n; // 정점의 전체 개수
for (int i = 0; i < n; i++) {
char str[80];
int val;
fp >> str; // 정점의 이름
insertVertex(str[0]); // 정점 삽입
for (int j = 0; j < n; j++) {
fp >> val; // 간선 정보
insertEdge(i, j, val); // 간선 삽입
}
}
}
else cout << "File can not be found !" << endl;
fp.close();
}
};
// Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프
class WGraphDijkstra : public WGraph {
int path[MAX_VTXS];
int dist[MAX_VTXS]; // 시작노드로부터의 최단경로 거리
bool found[MAX_VTXS]; // 방문한 정점 표시 집합 S -> 집합 포함 시 true
public:
int chooseVertex() { // 가장 비용 적은 미방문 정점을 반환
int min = INF;
int minpos = -1;
for (int i = 0; i < size; i++)
if (dist[i] < min && !found[i]) {
min = dist[i];
minpos = i;
}
return minpos;
}
void printDistance() { //모든 정점들의 dist[] 값 출력
for (int i = 0; i < size; i++) { cout << dist[i] << " "; }
cout << endl;
}
void PrintPath(int start, int end) {
cout << "[최단경로: " << getVertex(start) << "<-" << getVertex(end) << "] " << getVertex(end);
while (path[end] != start) {
cout << "-" << getVertex(path[end]);
end = path[end];
}
cout << "-" << getVertex(path[end]) << endl;
}
// Dijkstra의 최단 경로 알고리즘: start 정점에서 시작함.
void ShortestPath(int start) {
for (int i = 0; i < size; i++) { //초기화: dist[], found[]
dist[i] = getEdge(start, i); //인접행렬 값 반환(간선 가중치)
path[i] = start;
found[i] = false; //처음에 S집합은 비어있음.
}
found[start] = true; // S에 포함
dist[start] = 0; // 최초 거리
for (int i = 0; i < size; i++) {
cout << "Step" << i + 1 << ": ";
printDistance(); // 모든 dist[] 배열값 출력
int u = chooseVertex(); // S에 속하지 않은 비용 가장 작은 정점 반환
found[u] = true; // 집합 S에 u를 포함시킴
for (int w = 0; w < size; w++) {
if (found[w] == false)//S에 속하지 않는 노드 w의 dist값 갱신
if (dist[u] + getEdge(u, w) < dist[w]) {
dist[w] = dist[u] + getEdge(u, w);
path[w] = u;
}
} // u를 거쳐가는 것이 최단 거리이면 dist[] 갱신
}
}
};
int main() {
// 다익스트라
WGraphDijkstra g;
string fn = "graph_sp.txt";
g.load(fn);
cout << "Dijkstra의 최단경로 탐색을 위한 그래프 : " << fn << endl << endl;
g.display();
cout << "Shortest Path By Dijkstra Algorithm" << endl;
g.ShortestPath(0);
cout << endl;
g.PrintPath(0, 3);
return 0;
}
3. (옵션) 백준 문제 풀어보기
다익스트라 알고리즘 문제는 모두 다음과 같은 단계를 거친다.
1. 그래프를 구현하기 위해 행렬(벡터)와 큐를 선언한다.
2. 정점과 가중치 정보를 입력받아 행렬에 저장한다.
3. 다익스트라 알고리즘을 실행해 최단 경로를 탐색한다.
4. 문제에서 원하는 값을 출력한다.
이러한 4단계를 적용해 문제를 풀이한다.
● 1753 최단경로
→ 문제 풀이
1. 그래프를 구현하기 위한 행렬(벡터)와 큐를 선언한다.
2. 정점과 가중치 값들을 입력받아 행렬에 저장한다.
3. 큐가 비어있을 때까지 while문을 반복하며 탐색을 진행한다.
해당 노드와 연결된 노드들을 for문을 통해 돌며 가장 가중치가 작은 노드를
최단 경로 배열로 저장한다.
4. 저장한 최단 경로 배열을 하나씩 출력한다.
#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
vector<pair<int,int> > node[20005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
int value[20005];
int main(){
int n,e,k;
int u,v,w;
scanf("%d %d",&n,&e);
scanf("%d",&k);
for(int i=0;i<e;i++){
scanf("%d %d %d",&u,&v,&w);
node[u].push_back(make_pair(v,w));
}
for(int i=1;i<=n;i++)
value[i] = INF;
value[k] = 0;
pq.push(make_pair(0,k));
while(!pq.empty()){
int x = pq.top().first;
int U = pq.top().second;
pq.pop();
for(int i=0;i<node[U].size();i++){
int V = node[U][i].first;
int W = node[U][i].second;
if(x+W<value[V]){
value[V] = x+W;
pq.push(make_pair(x+W,V));
}
}
}
for(int i=1;i<=n;i++)
if(value[i]==INF) printf("INF\n");
else printf("%d\n",value[i]);
return 0;
}● 1238 파티
→ 문제 풀이
1. 그래프를 구현하기 위한 행렬(벡터)와 큐를 선언한다.
2. 두 정점과 가중치를 입력받아 그래프 정보로 벡터행렬에 저장한다.
3. 다익스트라 알고리즘을 실행해 큐가 비어있을 때까지 while문을 반복하며
탐색을 진행한다.
해당 노드와 연결된 노드들을 for문을 통해 돌며 가장 가중치가 작은 노드를
최단 경로 배열로 저장한다.
4. 왔다갔다하며 최단 거리들 중 가장 가중치 값이 큰 경우의 가중치를 출력한다.
#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;
int N, M, X;
const int INF = 1e9+7;
vector<pii > graph[2][1001];
vector<int> dist[2];
int resdist[1001];
void input(){
int u, v, t;
cin >> N >> M >> X;
for(int i = 0; i < M; i++){
cin >> u >> v >> t;
graph[0][u].push_back(make_pair(t, v));
graph[1][v].push_back(make_pair(t, u));
}
dist[0].resize(N+1, INF);
dist[1].resize(N+1, INF);
}
void Dijstra(int k){
dist[k][X] = 0;
priority_queue<pii, vector<pii >, greater<pii > > que;
que.push({0, X});
while(!que.empty()){
int min_cost = que.top().first;
int now = que.top().second;
que.pop();
if(min_cost > dist[k][now]) continue;
for(int i = 0; i < graph[k][now].size(); i++){
int next = graph[k][now][i].second;
int next_cost = min_cost + graph[k][now][i].first;
if(next_cost < dist[k][next]){
dist[k][next] = next_cost;
que.push({next_cost, next});
}
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
// 정점들에서 X로 가는 최단거리
Dijstra(1);
// X에서 정점들로 가는 최단거리
Dijstra(0);
int res = 0;
for(int i = 1; i <= N; i++){
res = max(res, dist[0][i] + dist[1][i]);
}
cout << res;
return 0;
}
● 1504 특정 최단 경로
→ 문제 풀이
1. 그래프를 구현하기 위한 행렬(벡터)와 큐를 선언한다.
2. 정점과 가중치 값들을 입력받아 행렬에 저장한다.
3. 다익스트라 알고리즘을 실행한다.
이 문제에서는 주어진 두 개의 정점을 무조건 지나는 최단 경로를 구해야한다.
따라서 아래와 같이 총 두가지의 경로가 나올 수 있다.
(1) start -> v1 -> v2 -> N
(2) start -> v2 -> v1 -> N
둘 중 더 짧은 경로를 선택해 출력한다.
이를 위해 각 경우의 수에서는 다익스트라 함수를 총 세 번 실행한다.
(1) start -> v1 를 구하기 위한 다익스트라.
v1 -> v2를 구하기 위한 다익스트라.
v2 -> N을 구하기 위한 다익스트라.
(2) start -> v2 를 구하기 위한 다익스트라.
v2 -> v1를 구하기 위한 다익스트라.
v1 -> N을 구하기 위한 다익스트라.
4. 두 가지 경우 중 비용이 더 적게 드는 경로의 길이를 출력한다.
가장 적게 드는 경로가 없다면 -1을 출력한다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 987654321;
int N, E, v1, v2, res = INF;
int sToV1, sToV2, V1ToV2, V1ToN, V2ToN;
vector<pair<int, int>> v[801]; // v[a] = (b,c) : a에서 b까지 c의 거리로 이동 가능
int dist[801];
void dijk(int start)
{
for (int i = 0; i <= N; i++) dist[i] = INF;
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({ 0,start }); // 현재까지 거리, 현재 위치
while (!q.empty()) {
int cur = q.top().second;
int curDist = q.top().first;
q.pop();
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i].first;
int nextDist = v[cur][i].second;
if (dist[next] > curDist + nextDist) {
dist[next] = curDist + nextDist;
q.push({ dist[next],next });
}
}
}
}
int main()
{
cin >> N >> E;
while (E--) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({ b,c });
v[b].push_back({ a,c });
}
cin >> v1 >> v2;
dijk(1);
sToV1 = dist[v1];
sToV2 = dist[v2];
dijk(v1);
V1ToV2 = dist[v2];
V1ToN = dist[N];
dijk(v2);
V2ToN = dist[N];
res = min(res, sToV1 + V1ToV2 + V2ToN);
res = min(res, sToV2 + V1ToV2 + V1ToN);
if (V1ToV2 == INF || res == INF) cout << -1;
else cout << res;
}
● 1916 최소비용 구하기
→ 문제 풀이
1. 그래프를 구현하기 위한 행렬(벡터)와 큐를 선언한다.
2. 정점과 가중치 값들을 입력받아 행렬에 저장한다.
3. 다익스트라 알고리즘을 실행한다.
큐가 비어있을 때까지 while문을 반복하며 탐색을 진행한다.
해당 노드와 연결된 노드들을 for문을 통해 돌며 가장 가중치가 작은 노드를
최단 경로 배열로 저장한다.
4. 최단 경로의 비용을 출력한다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
using pii= pair<int, int>;
vector<pii> vec[1001];
vector<int> dist(1001, INF);
void dijkstra(int dept){
dist[dept] =0;
priority_queue<pii> pq;
pq.push({dist[dept], dept}); // 시작 weight, vertex
while(!pq.empty()){
int cur = pq.top().second;
int distance = pq.top().first * -1; //현재까지 dept에서 cur 정점까지 가는 dist
pq.pop();
if(dist[cur]<distance) continue; //이미 distance가 최소로 변경됨
for(int i=0; i<vec[cur].size(); i++){
int nxt=vec[cur][i].first; //cur 정점과 연결된 정점들
int nxtdist = vec[cur][i].second + distance;
//현재까지 dept에서 cur정점까지의 최소 거리와
//cur을 지나 nxt까지의 거리를 더한것 cur정점에서 nxt까지의 distance
// e.g) 1 -> 4(cur) -> 5(nxt)
if(nxtdist<dist[nxt]){//만약 cur을 지나가는 것이 더 가깝다면
dist[nxt]= nxtdist;
pq.push({nxtdist*-1, nxt});//새롭게 갱신된 weight와 vertex
}
}
}
}
int main(){
int N, M; cin>>N>>M;//도시의 개수, 버스의 개수
while(M--){
int s, e, w; cin>>s>>e>>w;
vec[s].push_back({e, w});
}
int dept, dest;
cin>>dept>>dest;
dijkstra(dept);
cout<<dist[dest];
return 0;
}
4. (옵션) BFS 관련 문제를 풀어보기
● 주어진 데이터로 문제 풀어보기
→ 문제: Find the shortest path between 913 and 542 vertices.
→ 풀이
1. 그래프를 구현하기 위한 행렬(벡터)와 큐를 선언한다.
2. 정점과 가중치 값들을 입력받아 행렬에 저장한다.
3. 다익스트라 알고리즘을 수행해 913부터 542까지의 최단 경로를 찾아낸다.
큐가 비어있을 때까지 while문을 반복하며 탐색을 진행한다.
해당 노드와 연결된 노드들을 for문을 통해 돌며 가장 가중치가 작은 노드를
최단 경로 배열로 저장한다.
4. 저장한 최단 경로 배열을 하나씩 출력한다.
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_VTXS 100
#define INF 9999 // INF이면 간선없음
// 가중치 그래프를 표현하는 클래스
class AdjMatGraph {
protected:
int size;
char vertices[MAX_VTXS];
int adj[MAX_VTXS][MAX_VTXS];
public:
AdjMatGraph() { reset(); }
char getVertex(int i) { return vertices[i]; }
int getEdge(int i, int j) { return adj[i][j]; }
void setEdge(int i, int j, int val) { adj[i][j] = val; }
bool isEmpty() { return size == 0; }
bool isFull() { return size >= MAX_VTXS; }
void reset() {
size = 0;
for (int i = 0; i < MAX_VTXS; ++i)
for (int j = 0; j < MAX_VTXS; ++j)
setEdge(i, j, 0);
}
void insertVertex(char name) {
if (!isFull()) vertices[size++] = name;
else cout << "ERROR : 그래프 정점 개수 초과" << endl;
}
void insertEdge(int u, int v) {
setEdge(u, v, 1);
setEdge(v, u, 1);
}
void display() {
cout << size << endl;
for (int i = 0; i < size; ++i) {
cout << getVertex(i) << " ";
for (int j = 0; j < size; ++j)
cout << getEdge(i, j) << "\t";
cout << endl;
}
}
};
// 가중치 그래프를 표현하는 클래스
class WGraph : public AdjMatGraph {
public:
void insertEdge(int u, int v, int weight) {
if (weight > INF) weight = INF;
setEdge(u, v, weight);
}
bool hasEdge(int i, int j) { return (getEdge(i, j) < INF); }
void load(string filename) {
ifstream fp(filename);
if (fp.is_open()) {
int n, val;
fp >> n; // 정점의 전체 개수
for (int i = 0; i < n; i++) {
char str[80];
int val;
fp >> str; // 정점의 이름
insertVertex(str[0]); // 정점 삽입
for (int j = 0; j < n; j++) {
fp >> val; // 간선 정보
insertEdge(i, j, val); // 간선 삽입
}
}
}
else cout << "File can not be found !" << endl;
fp.close();
}
};
// Dijkstra알고리즘의 최단 경로 탐색 기능이 추가된 그래프
class WGraphDijkstra : public WGraph {
int path[MAX_VTXS];
int dist[MAX_VTXS]; // 시작노드로부터의 최단경로 거리
bool found[MAX_VTXS]; // 방문한 정점 표시 집합 S -> 집합 포함 시 true
public:
int chooseVertex() { // 가장 비용 적은 미방문 정점을 반환
int min = INF;
int minpos = -1;
for (int i = 0; i < size; i++)
if (dist[i] < min && !found[i]) {
min = dist[i];
minpos = i;
}
return minpos;
}
void printDistance() { //모든 정점들의 dist[] 값 출력
for (int i = 0; i < size; i++) { cout << dist[i] << " "; }
cout << endl;
}
void PrintPath(int start, int end) {
cout << "[최단경로: " << getVertex(start) << "<-" << getVertex(end) << "] " << getVertex(end);
while (path[end] != start) {
cout << "-" << getVertex(path[end]);
end = path[end];
}
cout << "-" << getVertex(path[end]) << endl;
}
// Dijkstra의 최단 경로 알고리즘: start 정점에서 시작함.
void ShortestPath(int start) {
for (int i = 0; i < size; i++) { //초기화: dist[], found[]
dist[i] = getEdge(start, i); //인접행렬 값 반환(간선 가중치)
path[i] = start;
found[i] = false; //처음에 S집합은 비어있음.
}
found[start] = true; // S에 포함
dist[start] = 0; // 최초 거리
for (int i = 0; i < size; i++) {
cout << "Step" << i + 1 << ": ";
printDistance(); // 모든 dist[] 배열값 출력
int u = chooseVertex(); // S에 속하지 않은 비용 가장 작은 정점 반환
found[u] = true; // 집합 S에 u를 포함시킴
for (int w = 0; w < size; w++) {
if (found[w] == false)//S에 속하지 않는 노드 w의 dist값 갱신
if (dist[u] + getEdge(u, w) < dist[w]) {
dist[w] = dist[u] + getEdge(u, w);
path[w] = u;
}
} // u를 거쳐가는 것이 최단 거리이면 dist[] 갱신
}
}
};
int main() {
// 다익스트라
WGraphDijkstra g;
string fn = "graph_sp.txt";
g.load(fn);
cout << "Dijkstra의 최단경로 탐색을 위한 그래프 : " << fn << endl << endl;
g.display();
cout << "Shortest Path By Dijkstra Algorithm" << endl;
g.ShortestPath(913);
cout << endl;
g.PrintPath(913, 542);
return 0;
}
'자료구조실습 수업' 카테고리의 다른 글
| [Project - 기말 발표] (0) | 2022.12.04 |
|---|---|
| [13주차 과제] (0) | 2022.12.04 |
| [9주차 과제] (0) | 2022.11.06 |
| [MID] 중간 프로젝트 (0) | 2022.10.16 |
| [4주차 과제] (0) | 2022.10.02 |