[BOJ] 18231 - 파괴된 도시

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

BOJ - 파괴된 도시

문제 유형: 해 구성하기, 그래프 이론

문제 난이도: Gold V

시간 제한: 2초

메모리 제한: 512MB

 

문제

저명한 역사학자 지수는 오래된 지도 한 장을 주웠다. 이 지도는 N개의 도시와 M개의 도로로 이루어져 있으며, 각 도시는 1부터 N까지 하나씩 번호가 매겨져있다. 지도에는 불에 탄 모습의 K개의 도시가 있었는데, 지수는 이 지도가 전쟁 당시 파괴된 도시를 표시한 지도임을 알아차렸다. 연구한 바에 의하면, 어떤 도시에 그 당시 사용했던 폭탄을 떨어뜨리면 이 도시를 포함하여 인접한 도시들은 전부 파괴된다고 한다.

지수는 이 사실을 토대로 당시 폭탄이 떨어진 지점들을 알아내기 위해 우리를 초대했다. 우리는 폭탄이 떨어진 지점들을 전부 알아내야 한다. 어떤 방법으로도 지도와 같은 모양이 나오지 않을 수 있다. 이 경우도 판별해보자.

 

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 2000)과 도로의 개수 M(1 ≤ M ≤ min(N×(N-1)/2, 100,000))이 주어진다.

그 다음 M개의 줄에는 도시 Ui와 Vi가 주어진다. (1 ≤ Ui, Vi ≤ N)

이는 도시 Ui와 Vi가 하나의 도로로 연결되었음을 의미한다. Ui와 Vi가 같은 경우는 없으며, 같은 도시 쌍을 잇는 도로는 최대 하나만 존재한다.

그 다음 줄에 파괴된 도시의 개수 K(1 ≤ K ≤ N)가 주어진다.

그 다음 줄에 파괴된 도시의 번호를 의미하는 K개의 정수 Pi(1 ≤ Pi ≤ N)가 공백으로 구분되어 주어진다. 파괴된 도시의 번호가 중복되는 경우는 없다.

 

출력

만약, 어떤 경우라도 지도와 같은 모양이 나오지 않는다면 -1을 출력하라.

그렇지 않은 경우, 첫째 줄에 폭탄이 떨어진 도시의 개수 T를 출력하라.

그 다음 줄에는 폭탄이 떨어진 도시의 번호를 의미하는 T개의 정수를 공백으로 구분하여 출력하라. 출력에 중복된 도시의 번호가 존재해선 안된다.

만약, 정답으로 가능한 경우가 여러 가지라면 그중 하나를 출력하라.

 

풀이

도시와 도로의 정보를 인접리스트로 받고, 파괴된 도시는 해시셋으로 받는다.

모든 경우의 수를 탐색하면서, 파괴된 도시들과 인접하거나 파괴된 도시인 투하지점들을 찾아서 아무 경우나 출력하면 된다.

하나도 못 찾았다면, -1을 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

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

    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    cin >> k;
    set<int> destroyed;
    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        destroyed.insert(d);
    }

    for (int i = 1; i <= n; i++) {
        if (destroyed.find(i) == destroyed.end()) {
            continue;
        }

        set<int> node_exists;
        vector<int> roots;
        for (int j = i; j <= n; j++) {
            if (destroyed.find(j) == destroyed.end()) continue;

            bool flag = true;
            for (const auto &node : adj[j]) {
                if (destroyed.find(node) == destroyed.end()) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                roots.emplace_back(j);
                node_exists.insert(j);
                for (const auto &node : adj[j]) {
                    if (node_exists.find(node) == node_exists.end()) {
                        node_exists.insert(node);
                    }
                }
            }

            if (destroyed.size() == node_exists.size()) {
                cout << roots.size() << "\n";
                for (const auto &root : roots) {
                    cout << root << " ";
                }
                cout << "\n";
                return 0;
            }
        }
    }

    cout << "-1\n";

    return 0;
}