[백준] 1506 경찰서

문제 링크

1506번: 경찰서

알고리즘

강한 연결 요소(SCC), 플로이드 와셜

풀이

도시 i 에 세운 경찰서가 도시 j 를 통제할 수 있으려면, i 에서 j 로 갔다가, 다시 돌아오는 경로가 존재해야 한다.

유향 그래프에서 정점 uv 에 대해 서로 갈 수 있는 경로가 있다면 강하게 연결되었다고 할 수 있다. 강한 연결 요소 알고리즘으로 DFS 기반 선형 시간 알고리즘인 코사라주 알고리즘을 사용했다.

코사라주 알고리즘은 SCC 분리 알고리즘으로 역방향 그래프가 원래 그래프와 정확히 같은 SCC를 갖는다는 사실을 이용한다.

  1. 순방향 그래프 G에서 DFS를 수행하는데 각 정점에 대한 DFS가 끝나면 해당 정점을 스택에 넣는다.
  2. 역방향 그래프 T에서 스택을 토대로 DFS를 수행하면 강한 연결 요소 집합들이 생긴다. 즉, 1에서 DFS가 가장 늦게 끝난 정점부터 수행한다.

시간 복잡도는 인접 리스트인 경우 O(V+E)O(V+E), 인접 행렬인 경우 O(V2)O(V^2)이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>

using namespace std;

const int MAX = 100;

int cost[MAX];
bool visited[MAX];
vector<int> graph[MAX];
vector<int> reverse_graph[MAX];
stack<int> st;

void visit(int u) {
    visited[u] = true;
    for (auto adj : graph[u])
        if (!visited[adj]) visit(adj);
    st.push(u);
}

int assign(int u) {
    int ret = cost[u];
    visited[u] = true;
    for (auto adj : reverse_graph[u])
        if (!visited[adj]) ret = min(ret, assign(adj));
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> cost[i];

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '1') {
                graph[i].push_back(j);
                reverse_graph[j].push_back(i);
            }
        }
    }

    for (int i = 0; i < n; i++)
        if (!visited[i]) visit(i);

    memset(visited, false, sizeof(visited));

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        if (!visited[u]) ans += assign(u);
    }

    cout << ans << endl;
    return 0;
}

정점의 수가 100이기 때문에 플로이드 와셜 알고리즘으로도 풀 수 있다. 모든 정점에 대해 갈 수 있는 모든 루트를 표시하고, 되돌아올 수 있는지 확인하면 된다.

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

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 100;

int cost[MAX];
bool route[MAX][MAX];
bool visited[MAX];

int dfs(int u, int n) {
    int ret = cost[u];
    visited[u] = true;
    for (int i = 0; i < n; i++)
        if (!visited[i] && route[u][i] && route[i][u])
            ret = min(ret, dfs(i, n));
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> cost[i];
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++)
            if (s[j] == '1') route[i][j] = 1;
    }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (route[i][k] && route[k][j]) route[i][j] = 1;

    for (int i = 0; i < n; i++)
        if (!visited[i]) ans += dfs(i, n);

    cout << ans << endl;
    return 0;
}

Written by@WOOJIN
自强不息,厚德载物

GitHub