예제

15723번: n단 논법

개념

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

Dijkstra, Bellman-Ford알고리즘와 같은 길찾기 알고리즘 중 하나이다.

Floyd-Warshall 알고리즘을 이용하면 모든 정점에서 모든 정점으로 가는 최단 경로를 구할 수 있다.

Warshall알고리즘은 접근 가능여부만 판단한다.

간단한 과정 요약

만약 X에서 Y로 가는 최단 거리 $dist(X, Y)$를 구한다고 해보자. 중간지점 K에 대하여 $dist(X, Y)$와 $dist(X, K) + dist(K, Y)$를 비교하여 더 작은 값을 $dist(X, Y)$로 저장한다. 이 과정을 모든 K, Y, X에 대해 반복한다.

for루프를 작성하는 순서는 중간 → 시작 → 도착으로 해야한다.

C++

15723번 'n단 논법'

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool pre[26][26];
vector<pair<char, char>> con;
vector<pair<char, char>>::iterator it;

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

    int n, m;
    char a, b;
    string is;
    cin >> n;
    while (n--) {
        cin >> a >> is >> b;
        pre[a - 'a'][b - 'a'] = true;
    }
    cin >> m;
    while (m--) {
        cin >> a >> is >> b;
        con.push_back({a, b});
    }

    // Warshall
    for (int k = 0; k < 26; k++) {
        for (int i = 0; i < 26; i++) {
            if (!pre[i][k]) continue;
            for (int j = 0; j < 26; j++) {
                if (!pre[k][j]) continue;
                pre[i][j] = true;
            }
        }
    }
    for (it = con.begin(); it != con.end(); it++) {
        a = (*it).first - 'a';
        b = (*it).second - 'a';
        if (pre[a][b])
            cout << "T\\n";
        else
            cout << "F\\n";
    }
}

13424번 '비밀 모임'문제

#include <iostream>
#include <vector>

#define inf 10000000

using namespace std;

int map[101][101];
int dist[101];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        dist[i] = 0;
        for (int j = 1; j <= n; j++) {
            map[i][j] = inf;
        }
        map[i][i] = 0;
    }
}

void solve() {
    int n, m, k;
    int a, b, c;
    cin >> n >> m;
    init(n);
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        map[a][b] = c;
        map[b][a] = c;
    }
    cin >> k;
    vector<int> fri(k);
    vector<int>::iterator it;
    for (int i = 0; i < k; i++) {
        cin >> fri[i];
    }
    // Floyd Warshall
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (map[i][k] == inf) continue;
            for (int j = 1; j <= n; j++) {
                if (map[k][j] == inf) continue;
                if (map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
            }
        }
    }
    //
    int min_dist = inf;
    int min_room = -1;
    for (int i = 1; i <= n; i++) {
        for (it = fri.begin(); it != fri.end(); it++) {
            k = *it;
            dist[i] += map[k][i];
        }
        if (min_dist > dist[i]) {
            min_dist = dist[i];
            min_room = i;
        }
    }
    cout << min_room << '\\n';
}

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

    int testacase;
    cin >> testacase;
    while (testacase--) {
        solve();
    }
}