[BOJ] 1119 - 그래프

https://www.acmicpc.net/problem/1119

BOJ - 그래프

문제 유형: 그래프, MST(최소 신장 트리), dfs/bfs

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 128MB

 

문제

N개의 도시가 있고, 몇몇 도시들이 양방향 도로로 연결되어 있는 나라가 있다. 은진이는 이나라의 도로 몇 개를 수정해서 모든 도시가 서로 연결되어 있게 하려고 한다. 이때, 도로를 수정하는 회수를 최소로 하려고 한다. 도로를 수정하는 방법은 다음과 같다.

1. A와 B가 연결되어 있고, C와 D가 연결되어 있으면서, A와 C, A와 D, B와 C, B와 D가 연결되어 있지 않은 4개의 도시 A, B, C, D를 선택한다.
2. A와 B를 연결하는 도로와 C와 D를 연결하는 도로를 없앤다.
3. A와 C, B와 D를 연결하거나 A와 D, B와 C를 연결한다.

다음 그림을 살펴보자.

위와 같은 도로가 있을 때 이것을 다음에 보이는 둘 중에 하나로 바꿀 수 있다.

N이 주어지고, 각 도로의 정보가 주어진다. 이때, 몇 개의 도로를 수정해야 하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다 N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 도로의 정보가 주어진다. 인접행렬형식으로 표현되어 있으며 예제를 참고하자. g[i][j] = g[j][i]이고, g[i][i] = N이다.

 

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

 

풀이

처음에는 3길이 이상 사이클이 있는 연결컴포넌트가 2길이짜리 또는 비사이클 연결컴포넌트와 결합 시에 비사이클 연결컴포넌트가 되는 줄 알았는데, 다른 더 있으면 여전히 3길이 이상 사이클을 가질 수 있다는 걸 나중에야 알았다..

 

만약 하나의 연결컴포넌트가 내부에서 최소신장트리를 구성하고, 나머지 간선들을 추가로 가지고 있다면, 그 개수만큼 비사이클의 연결컴포넌트들과 결합할 수 있다.

안정적인 연결컴포넌트들끼리는, 즉 추가 간선들의 여유가 있는 컴포넌트들끼리는 결합에 제약이 없다.

 

결론은, 그래프 전체의 이러한 여유분 간선들의 개수가 (연결 컴포넌트들의 개수-1)보다 크거나 같다면, (연결 컴포넌트들의 개수-1)이 답이라는 것이다. 부족하면 구성할 수 없다.

단, N=1인경우, 답이 0이다.

 

이외에도, 고립된 노드(연결된 노드가 하나도 없는 경우)가 하나라도 나올시 불가능하다.

 

구현은 BFS로 간선개수를 세주고, 2를 나눠서 방향성을 없애준 뒤, (정점의 수-1)를 빼서 남는 간선들의 개수를 누적했다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    string temp;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < n; j++) {
            if (temp[j] == 'Y') adj[i].emplace_back(j);
        }
    }

    if (n == 1) {
        cout << "0\n";
        return 0;
    }

    bool isolatedNode = false;
    int components = 0;
    int extraEdges = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            components++;
            if (adj[i].empty()) {
                isolatedNode = true;
                break;
            }

            int vertexes = 0;
            int edges = 0;
            queue<int> q;
            q.emplace(i);
            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                vertexes++;
                edges += adj[curr].size();

                for (const auto& next : adj[curr]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.emplace(next);
                    }
                }
            }

            extraEdges += (edges / 2) - (vertexes - 1);
        }
    }

    if (extraEdges >= components - 1 && !isolatedNode) {
        cout << components - 1 << "\n";
    } else {
        cout << "-1\n";
    }

    return 0;
}