10. 최단경로, 플로이드-와샬, 다익스트라

10.md

0.01MB

0. 복습

1. 최단경로

그래프에서 최단경로를 찾고 싶으면 어떡할까?

다익스트라, 벨만-포드, 플로이드-와샬 등등을 사용할 수 있다.

그 중 이번시간엔 다익스트라와 플로이드를 해본다.

2. 플로이드-와샬 (Floyd-Warshall)

줄여서 그냥 플로이드라고 하자.

일단 최단경로 알고리즘의 일종인 플로이드는 최단경로 알고리즘 중 가장 짧고 간단한 알고리즘이다.

#include <iostream>
using namespace std;
int dp[100][100];
const int INF = 1e9;

int main(){
    int N, M; cin >> N >> M;
    for(int i=0; i<N; ++i){
        for(int j=0; j<M; ++j){
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    //초기화 : 자기 자신은 0, 나머지는 INF(무한)
    //입력단계에서 dp[i][j] : i에서 j까지의 거리
    for(int i=0; i<M; ++i){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        dp[u][v] = min(dp[u][v], w);
    }

    for(int k=0; k<N; ++k){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    //dp갱신 후 dp[i][j] : i에서 j까지의 최단거리

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(dp[i][j] == INF) cout << 0 << ' ';
            else cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
}

k가 0일 때 모든 경로에 대해 0이 끼어들 수 있는지 탐색한다.

k가 1일 때 모든 경로에 대해 1이 끼어들 수 있는지 탐색한다.

k가 2일 때 모든 경로에 대해 2가 끼어들 수 있는지 탐색한다.

...

N까지 반복하면 모든 경로에 대해 최단경로가 나온다.

시간복잡도는 O(N^3)이다.

3. 다익스트라(dijkstra)

기본 지식 : priority_queue, dp, graph

시간복잡도는 O(ElogE)이다.

//bfs랑 비슷함.
#include <iostream>
#include <queue>
using namespace std;

const int MN = 2e4;
const int INF = 1e9;

struct edge {
    int v, w; // v : 어디까지 갈지, w : 가중치
    edge(int v, int w) : v(v), w(w) {} // 생성자
};

vector<edge> G[MN];
int dist[MN];

int main(){
    int N, M; cin >> N >> M;
    int K; cin >> K;
    K--;

    for(int i=0; i<M; ++i){
        int u, v, w;   cin >> u >> v >> w;
        u--, v--;
        G[u].push_back(edge(v, w));
    }

    for(int i=0; i<N; ++i){
        dist[i] = INF;
    }

    using P = pair<int, int>; //typedef pair<int, int> P;
    priority_queue<P, vector<P>, greater<P> > pq; // first : 해당 정점까지의 거리, second : 해당 정점.
    pq.push(make_pair(0, K));
    dist[K] = 0; // K에서부터 해당 정점까지의 최단 경로가 들어감.
    //Priority_queue에서 (D, V)를 뽑았다면, 시작점에서 V까지의 최단거리는 무조건 D이다.

    while(!pq.empty()) {
        P top = pq.top(); pq.pop();
        int cur_dist = top.first;
        int cur = top.second;

        if(dist[cur] < cur_dist) continue;
        for(edge nxt_edge : G[cur]) {
            int nxt = nxt_edge.v;
            if(dist[nxt] > dist[cur] + nxt_edge.w) { // 지금 있는 정점(cur)을 거쳐서 가는 게 더 짧으면 갱신.
                dist[nxt] = dist[cur] + nxt_edge.w;
                pq.push(make_pair(dist[nxt], nxt));
            }
        }
    }

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

99. 참고 문제

14940, 7562, 11404, 11403, 1753, 9205

참고 문제 풀이
boj.kr/14940

#include <iostream>
#include <queue>
using namespace std;
int arr[1000][1000];
int res[1000][1000];
bool visited[1000][1000];
int di[4]={-1, 0, 1, 0};
int dj[4]={0, -1, 0, 1};
int si, sj;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;   cin >> n >> m;
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            cin >> arr[i][j];
            if(arr[i][j] == 2){
                si=i, sj=j;
            }
        }
    }
    queue<pair<int, pair<int, int> > > q;
    visited[si][sj] = true;
    q.push({0, {si, sj}});
    while(!q.empty()){
        pair<int, pair<int, int> > F = q.front();
        q.pop();
        res[F.second.first][F.second.second] = F.first;
        for(int d=0; d<4; ++d){
            int ni=F.second.first+di[d];
            int nj=F.second.second+dj[d];
            if(ni>=0 && ni<n && nj>=0 && nj<m) {
                if(!visited[ni][nj] && arr[ni][nj]==1) {
                    q.push({F.first+1, {ni, nj}});
                    visited[ni][nj]=true;
                }
            }
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(arr[i][j]==1 && res[i][j] == 0) cout << "-1" << ' ';
            else cout << res[i][j] << ' ';
        }
        cout << '\n';
    }
}

boj.kr/7562

#include <iostream>
#include <queue>
using namespace std;
int di[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dj[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
bool visited[300][300];

int main() {
    int T; cin >> T;
    while (T--) {
        int l; cin >> l;
        int a, b, c, d; 
        cin >> a >> b;
        cin >> c >> d;
        queue<pair<int, pair<int, int> > > q;
        q.push({ a, {b, 0} });
        for (int i = 0; i < 300; ++i) {
            for (int j = 0; j < 300; ++j) {
                visited[i][j] = false;
            }
        }
        visited[a][b] = true;
        while (!q.empty()) {
            pair<int, pair<int, int> > F = q.front();
            q.pop();
            if (F.first == c && F.second.first == d) {
                cout << F.second.second << '\n';
                break;
            }
            for (int d = 0; d < 8; ++d) {
                    int ni = F.first + di[d];
                    int nj = F.second.first + dj[d];
                    if (ni >= 0 && ni < l && nj >= 0 && nj < l) {
                        if (!visited[ni][nj]) {
                            q.push({ ni, {nj, F.second.second+1} });
                            visited[ni][nj] = true;
                        }
                    }
            }
        }
    }
}

boj.kr/11404

#include <iostream>
using namespace std;
int dp[100][100];
const int INF = 1e9;

int main(){
    int N, M; cin >> N >> M;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    //초기화 : 자기 자신은 0, 나머지는 INF(무한)
    //입력단계에서 dp[i][j] : i에서 j까지의 거리
    for(int i=0; i<M; ++i){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        dp[u][v] = min(dp[u][v], w);
    }

    for(int k=0; k<N; ++k){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    //dp갱신 후 dp[i][j] : i에서 j까지의 최단거리

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(dp[i][j] == INF) cout << 0 << ' ';
            else cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
}

boj.kr/11403

#include <iostream>
using namespace std;
int dp[100][100];
const int INF = 1e9;

int main(){
    int N; cin >> N;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }
    //초기화 : 자기 자신은 0, 나머지는 INF(무한)
    //입력단계에서 dp[i][j] : i에서 j까지의 거리
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cin >> dp[i][j];
            if(dp[i][j] == 0) dp[i][j] = INF;
        }
    }

    for(int k=0; k<N; ++k){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    //dp갱신 후 dp[i][j] : i에서 j까지의 최단거리

    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(dp[i][j] == INF) cout << 0 << ' ';
            else cout << 1 << ' ';
        }
        cout << '\n';
    }
}

boj.kr/1753

//bfs랑 비슷함.
#include <iostream>
#include <queue>
using namespace std;

const int MN = 2e4;
const int INF = 1e9;

struct edge {
    int v, w; // v : 어디까지 갈지, w : 가중치
    edge(int v, int w) : v(v), w(w) {} // 생성자
};

vector<edge> G[MN];
int dist[MN];

int main(){
    int N, M; cin >> N >> M;
    int K; cin >> K;
    K--;

    for(int i=0; i<M; ++i){
        int u, v, w;   cin >> u >> v >> w;
        u--, v--;
        G[u].push_back(edge(v, w));
    }

    for(int i=0; i<N; ++i){
        dist[i] = INF;
    }

    using P = pair<int, int>; //typedef pair<int, int> P;
    priority_queue<P, vector<P>, greater<P> > pq; // first : 해당 정점까지의 거리, second : 해당 정점.
    pq.push(make_pair(0, K));
    dist[K] = 0; // K에서부터 해당 정점까지의 최단 경로가 들어감.
    //Priority_queue에서 (D, V)를 뽑았다면, 시작점에서 V까지의 최단거리는 무조건 D이다.

    while(!pq.empty()) {
        P top = pq.top(); pq.pop();
        int cur_dist = top.first;
        int cur = top.second;

        if(dist[cur] < cur_dist) continue;
        for(edge nxt_edge : G[cur]) {
            int nxt = nxt_edge.v;
            if(dist[nxt] > dist[cur] + nxt_edge.w) { // 지금 있는 정점(cur)을 거쳐서 가는 게 더 짧으면 갱신.
                dist[nxt] = dist[cur] + nxt_edge.w;
                pq.push(make_pair(dist[nxt], nxt));
            }
        }
    }

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

boj.kr/9205

#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int dp[105][105];
int abs_(int a, int b){
    if(a>b) return a-b;
    else return b-a;
}
int main(){
    int T; cin >> T;
    while(T--){
        vector<pair<int, int> > v;
        int n; cin >> n;
        int x, y;
        for(int i=0; i<n+2; ++i){
            cin >> x >> y;
            v.push_back({x, y});
        }
        for(int i=0; i<n+2; ++i){
            for(int j=0; j<n+2; ++j){
                if(i==j) dp[i][j] = 0;
                else {
                    if(abs_(v[i].first, v[j].first) + abs_(v[i].second, v[j].second) <=1000){
                        dp[i][j] = 1;
                        dp[j][i] = 1;
                    }
                    else {
                        dp[i][j] = INF;
                        dp[j][i] = INF;
                    }
                }
            }
        }
        for(int k=0; k<n+2; ++k){
            for(int i=0; i<n+2; ++i){
                for(int j=0; j<n+2; ++j){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        if(dp[0][n+1] == INF) cout << "sad" <<'\n';
        else cout << "happy" << '\n';
    }
}