백준 18231 (파괴된 도시) - java

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

18231번: 파괴된 도시

 

문제

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

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

 

유형 : 그래프 탐색

 

전체 코드

import java.util.*;
import java.io.*;
public class Main {

    static int n = 0;
    static int m = 0;

    static int k = 0;

    static ArrayList<Integer>[] graph;

    static boolean[] isIt;

    static boolean[] v;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n+1];
        isIt = new boolean[n+1];
        v = new boolean[n+1];

        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(bf.readLine(), " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[x].add(y);
            graph[y].add(x);
        }

        k = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine(), " ");

        for(int i=1;i<=k;i++){
            int cur = Integer.parseInt(st.nextToken());

            isIt[cur] = true;
        }

        ArrayList<Integer> result = new ArrayList<>();

        for(int i=1;i<=n;i++){

            if(isIt[i]){

                boolean find = true;

                for(int next : graph[i]){
                    if(!isIt[next]){
                        find = false;
                        break;
                    }
                }

                if(find){
                    result.add(i);
                }

            }
        }

        int count = 0;

        for(int cur : result){

            if(!v[cur]){
                v[cur] = true;
                count += 1;
            }

            for(int next : graph[cur]){

                if(!v[next] && isIt[next]){
                    v[next] = true;
                    count += 1;
                }

            }
        }

        StringBuilder sb = new StringBuilder();

        if(result.size() == 0 || count != k){
            sb.append(-1+"\n");
        }else {
            sb.append(result.size()+"\n");
            for (int cur : result) {
                sb.append(cur + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
        bf.close();
    }


}