[이취코] 9. 최단경로 - C++

1. 다익스트라 : 시작 정점 하나로부터 다른 모든 정점으로 가는 최단 경로 찾기 (bfs와 비슷, 비용이 있음 => visit 대신) O(E logV)

dist : 1차원 배열(INF로 초기화), idx : 1부터 시작, 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n = 6, m, start;
#define INF 1e9
int a, b, c;
vector<pair<int, int>> graph[7]; //노드 간 간선
int d[7]; //최소 비용

void dijkstra(int start) {  //노드 순서 작은 것, 만약 거리를 작은 순으로 하고 싶으면 pq, arr에 들어가는 순서 바꿔야함
    d[start] = 0;
    priority_queue<pair<int, int>> pq; //가까운 순서대로 처리하므로
    pq.push({start, 0});

    while (!pq.empty()) {
        int current = pq.top().first;
        int distance = -pq.top().second; //짧은 것이 먼저 오도록 음수화
        pq.pop();

        cout << "cur: " << current << ", 현재 거리: " << d[current] << ", 바꾸려는 거리:  " << distance << endl;

        if (d[current] < distance) //최단 거리가 아닌 경우
            continue;

        for (auto &i: graph[current]) { //선택된 노드의 인접 노드
            int next = i.first;
            int nextDistance = distance + i.second;
            cout << "next: " << next << ", " << nextDistance << "\n";

            if (nextDistance < d[next]) {    //기존의 최소 비용보다 더 저렴하다면 교체
                pq.push({next, -nextDistance});
                d[next] = nextDistance;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    for (int i = 1; i <= n; i++) { //연결되지 않은 경우 비용은 무한
        d[i] = INF;
    }

    graph[1].emplace_back(2, 2);
    graph[1].emplace_back(3, 5);
    graph[1].emplace_back(4, 1);

    graph[2].emplace_back(1, 2);
    graph[2].emplace_back(3, 3);
    graph[2].emplace_back(4, 2);

    graph[3].emplace_back(1, 5);
    graph[3].emplace_back(2, 3);
    graph[3].emplace_back(4, 3);
    graph[3].emplace_back(5, 1);
    graph[3].emplace_back(6, 5);

    graph[4].emplace_back(1, 1);
    graph[4].emplace_back(2, 2);
    graph[4].emplace_back(3, 3);
    graph[4].emplace_back(5, 1);

    graph[5].emplace_back(3, 1);
    graph[5].emplace_back(4, 1);
    graph[5].emplace_back(6, 2);

    graph[6].emplace_back(3, 5);
    graph[6].emplace_back(5, 2);

    dijkstra(1);

    // [ 입력받도록 하는 코드 ]
    //cin >> n >> m >> start; //노드 개수, 간선정보 개수, 시작 노드
    //for (int i = 1; i <= n; i++) {
    //    d[i] = INF;
    //}
    //while (m--) {
    //    cin >> a >> b >> c;
    //    graph[a].push_back({b, c});
    //}
    //dijkstra(start);

    return 0;
}
//6 20 1
//1 2 2
//1 3 5
//1 4 1
//2 1 2
//2 3 3
//2 4 2
//3 1 5
//3 2 3
//3 4 3
//3 5 1
//3 6 5
//4 1 1
//4 2 2
//4 3 3
//4 5 1
//5 3 1
//5 4 1
//5 6 2
//6 3 5
//6 5 2

 

2. 플로이드 : 모든 정점에서 최단 경로 찾음, k가 거쳐가는 중심 O(N^3)

dist : 2차원 배열(INF로 초기화), idx : 1부터 시작

#include <iostream>
using namespace std;

#define INF 1000000001 //정점 100 x 비용 10만
#define MAX 102
int dist[MAX][MAX];
int n, m, a, b, c;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
        }
    }

    while (m--) {
        cin >> a >> b >> c;
        if (dist[a][b] > c) {
            dist[a][b] = c;
        }
    }

    for (int k = 1; k <= n; k++) { //거쳐가는게 중심
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] == INF || dist[k][j] == INF) {
                    continue;
                }

                // i에서 k로 가는비용 + k에서 j로 가는비용 vs i에서 j로 가는 비용
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] == INF || i == j) {
                cout << "0 ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << "\n";
    }

    return 0;
}
//4 7
//1 2 4
//1 4 6
//2 1 3
//2 3 7
//3 1 5
//3 4 4
//4 3 2

//결과
//0 4 8 6
//3 0 7 9
//5 9 0 4
//7 11 2 0

3. 벨만 포드 : 가중치 음수인 문제에서 사용 -> 거의 안나옴

4. BFS : 넓이 우선 탐색(가중치가 1인 문제에서의 최단 경로) O(N+E)

dist : 2차원 배열 , idx : 0부터 시작

 

1) 그래프일 경우

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define MAX 1002
int graph[MAX][MAX];
bool visit[MAX];
int n, m , k, a, b;
int dist[MAX];

void BFS(int V) {
	queue<int> Q;
	Q.push(V);
	visit[V] = 1;
	while (!Q.empty()) {
		V = Q.front();
		Q.pop();
		
		for (int i = 1; i <= n; i++) {
			if (graph[V][i] == 1 && !visit[i]) {//간선이 존재하고 방문하지 않은 경우
				Q.push(i);
				visit[i] = 1;
				dist[i] = dist[V] + 1;
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	
	while(m--){
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	BFS(1);
	
	if(dist[n] > 0 && dist[n]<= k ){ //갈 수 있고 k보다 작을 경우
		cout << "YES";
	} else{
		cout << "NO";
	}
	
	return 0;
}

 

2) 행렬일 경우 (4방향)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
int map[102][102];
bool visit[102][102];
int check[102][102];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(int x, int y) {
    visit[x][y] = true;

    queue<pair<int, int>> q;
    q.push({x, y});

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (!visit[nx][ny] && map[nx][ny] == 1) {
                visit[nx][ny] = true;
                q.push({nx, ny});
                check[nx][ny] = check[x][y] + 1;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    char c;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c;
            map[i][j] = c - '0';
        }
    }

    bfs(0, 0);
    cout << check[n - 1][m - 1] + 1; //0, 0으로 시작하면 count가 원래 0 -> 1
    return 0;
}
//4 6
//110110
//110110
//111111
//111101

//결과 (최단경로)
//9

9-4. 미래도시

1부터 k거치고 x까지의 최단거리 구해라 (100^3해도 백만이라 1초 가능)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 1e9
int n, m, x, k, a, b;
int dist[101][101];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = INF;
        }
    }

    while (m--) {
        cin >> a >> b;
        dist[a][b] = 1;
        dist[b][a] = 1;
    }
    cin >> x >> k;

    for (int z = 1; z <= n; z++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][z] == INF || dist[z][j] == INF)
                    continue;
                if (dist[i][z] + dist[z][j] < dist[i][j])
                    dist[i][j] = dist[i][z] + dist[z][j];
            }
        }
    }

    if (dist[1][k] + dist[k][x] >= INF)
        cout << -1;
    else
        cout << dist[1][k] + dist[k][x];
    return 0;
}

 

9-5. 전보

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 1e9
int n, m, C, a, b, c;
int dist[30001];
vector<pair<int, int>> graph[30001];

void dijkstra(int start) {
    dist[start] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        int current = pq.top().second;
        int distance = -pq.top().first;
        pq.pop();

        if (dist[current] < distance)
            continue;

        for (auto &i: graph[current]) {
            int next = i.second;
            int nextDistance = distance + i.first;

            if (nextDistance < dist[next]) {
                pq.push({-nextDistance, next});
                dist[next] = nextDistance;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> C;

    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    while (m--) {
        cin >> a >> b >> c;
        graph[a].emplace_back(c, b);
    }
    dijkstra(C);

    int result = 0;
    int maxDistance = 0;

    for (int i = 1; i <= n; i++) {
        if (dist[i] != INF) {  //INF 아닌 거 개수 = C에서 도달할 수 있는 노드 cnt
            result += 1;
            maxDistance = max(maxDistance, dist[i]); //가장 먼 시간
        }
    }
    cout << result - 1 << " " << maxDistance;
    return 0;
}