[ boj : 18231 ] 파괴된 도시

안녕하세요ㅎㅎ....
알고리즘 관련 글을 안쓰겠다고 했는데 ㅠㅠㅠ 어쩔 수 없나보네용

바로 문제 해설 들어가겠습니다.

정점 n 과 간선 v 의 그래프가 주어지고 k 만큼 파괴된 도시가 존재한 지도가 주어집니다.

도시가 파괴되었다는 뜻은 2가지 상황이 발생할 수 있는데

1) 직접 폭탄이 파괴된 도시에 떨어졌던가
2) 인접한 도시에 폭탄이 떨어졌던가

이렇게 2가지 상황이 존재할 수 있습니다.

문제에서 최소개수의 폭탄을 구해라!!! 라는 것이 아니라 그냥 지도의 가능여부와 가능하다면 폭탄의 개수, 폭탄이 떨어진 도시만 출력하면 된다고 했습니다.

그러면 그냥 맘편하게 개수는 필요없으니 될 수 있는대로 많이 폭탄이 떨어진 걸로 가정해보자고요

파괴된 도시가 존재하면 인접한 도시가 멀쩡한지 안한지 부터 검사합니다.
만약 멀쩡한 도시가 존재한다면 현재 위치한 도시에 폭탄이 떨어지지 않았음을 의미하죠?

저장공간 2개를 선언합시다.(전 set,vector 이렇게 선언했습니다;;ㅎㅎ)
그리고 한쪽에는 인접한 도시가 전부 파괴된 정점 - a
다른한쪽에는 인접한 도시가 하나라도 멀쩡한 도시가 있는 정점 - b

그러면 b 에 존재하는 정점들은 단 한개라도 a 에 속해 있는 정점과 인접해야지만 유효한다는 것을 알 수 있습니다.
만약 b 에 존재하는 정점들 중 단 한개라도 a 에 속해 있지 않다면 이 지도는 잘못된 지도임을 뜻하는 거죠

그럼 끝났습니다.
위 로직처럼 그대로 코딩만 해주면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf = (ll)1e9;
const int SIZE = 2010;

int n, m;
vector<int> adj[SIZE];
set<int> st;
int dest[SIZE];

void solve();
bool dfs(int x);

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

    int t = 1;
    //cin >> t;
    //while (t--)
    solve();
    return 0;
}
void solve() 
{
    cin >> n >> m;
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> u;
        dest[u] = 1;
    }

    set<int> A;
    vector<int> B;
    for (int i = 1; i <= n; i++) {
        if (dest[i]) {
            if (!dfs(i))A.insert(i);
            else B.push_back(i);

        }
    }

    bool ans = false;
    for (int u : B) {
        bool flag = true;
        for (int p : adj[u]) {
            if (A.find(p) != A.end()) {
                flag = false;
            }
        }
        if (flag)ans = true;
    }

    if (ans)cout << -1;
    else {
        cout << A.size() << "\n";
        for (int u : A)
            cout << u << " ";
    }
}
bool dfs(int x)
{
    bool flag = false;
    for (int u : adj[x]) {
        if (!dest[u])
            flag = true;
    }
    return flag;
}