[Java] 폭탄 제거

1. 문제 설명

n개의 폭탄이 주어진다. 폭탄은 1~N으로 번호가 붙혀져 구분되며 특정 폭탄은 다른 폭탄이 해체되면 폭발하도록 설정되어 있었다.
A라는 폭탄이 해체되었을 때 B라는 폭탄이 자동으로 폭발한다는 관계를 A->B라고 정의하면 7개의 관계는 다음과 같다
1 -> 2 -> 3 -> 4 -> 5, 6 -> 7 의 폭탄을
7-> 6, 5 -> 4 -> 3 -> 2 -> 1 순서로 해체 가능

그러나 위와 같이 3 -> 7 -> 6 -> 2의 경우 3을 해체하면 7이 폭발하니 해제 방법이 없다
위 설명을 토대로 폭탄 해체 가능 여부를 구하라\

입력 형식

첫 줄에는 테스트케이스의 수를 나타내는 10이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 아래와 같은 형식으로 주어진다.

각 테스트케이스의 첫 줄에는 두 개의 자연수가 공백으로 구분되어 N M형식으로 주어진다.

N은 폭탄의 수를 나타내는 2이상 10만이하의 자연수다.
M은 폭탄들의 연쇄 관계의 수를 나타내는 10만이하의 자연수다.
이후 총 M줄에 걸쳐서 각 줄마다 두 개의 자연수가 공백으로 구분되어 U V형식으로 주어진다.

각 줄은 폭탄 U가 해체되면 폭탄 V가 폭발하도록 설정되었다는 것을 나타낸다.

출력 형식

각 테스트케이스에 대하여 한 줄에 정답을 출력한다.

해당 테스트케이스에 대하여 모든 폭탄을 성공적으로 해체할 수 있는 방법이 존재한다면 YES를 출력한다.
그렇지 않다면 NO를 출력한다.

2. 알고리즘 접근

그래프와 인접 리스트(Adjacency List)

단방향으로 관계가 지정되어 있으니 각 간선의 연결 정보를 각 노드에 저장하고, 모든 노드의 정보를 하나의 리스트로 표현하면 전체 그래프를 리스트로 표현할 수 있다.
-> 이를 응용하자

U가 해체되면 V가 폭발한다. -> U, V 모두 해체하기 위해서는 V를 먼저 해체한다.
1 -> 2 -> 3 -> 4 -> 5, 6 -> 7이 있다면
각 노드에 대해서 자신을 폭발시킬 노드와, 내가 폭발시킬 노드의 개수를 리스트로 표현해 이를 처리한다

3. 소스코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Q5E {
    // 폭탄 제거
    static final Scanner sc = new Scanner(System.in);
    private static boolean isAllRemovable(int n, Bomb[] bombs) {

        // 제거해도 상관없는 폭탄
        Queue<Bomb> removableBombs = new LinkedList<>();

        // 제거 완료된 폭탄
        ArrayList<Bomb> removedList = new ArrayList<>();

        for (Bomb b : bombs){ // 모든 폭탄에 대해
            if(b.getChildCount() == 0){
                removableBombs.add(b);
            }
        }

        while (removableBombs.size() > 0){
            Bomb b = removableBombs.poll(); // 제거 가능 폭탄을 꺼낸다
            b.remove(); // 제거 가능한 폭탄을 제거 (Parent Bomb의 카운트를 1감소)
            removedList.add(b); // 제거 완료 리스트에 추가

            for(Bomb p : b.getParentBombs()){ // 제거 가능폭탄의 ParentBomb를 가져와
                if(p.getChildCount() == 0){
                    // 그 값이 0이면 제거 가능한 값이 된다
                    removableBombs.add(p);
                }
            }
        }
        if(removedList.size() == n){ // 제거한 개수가 폭탄수와 같으면 true
            return true;
        }else {
            return false;
        }

    }

    private static void testCase(int caseIndex) {
        int n = sc.nextInt(); // 폭탄 수
        int m = sc.nextInt(); // 연쇄 관계 수

        Bomb[] bombs = new Bomb[n];
        for(int i = 0; i < n; i++){
            bombs[i] = new Bomb(i); // 각 폭탄에 대한 초기화
        }

        for(int i = 0; i < m; i++){
            int u = sc.nextInt() - 1; // u가 해제되면
            int v = sc.nextInt() - 1; // v가 폭발한다

            Bomb b = bombs[v];
            b.addParentBombs(bombs[u]); // v에 u가 폭발을 유발할 수 있는 리스트임을 추가한다
        }
        boolean removable = isAllRemovable(n, bombs);

        if(removable) {
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }

    public static void main(String[] args) {
        int caseSize = sc.nextInt();
        for(int caseIndex = 1; caseIndex <= caseSize; caseIndex++){
            testCase(caseIndex);
        }
    }
}
class Bomb{
    private int index;
    private int childCount; // 이 폭탄이 터졌을 때 함께 폭발하는 폭탄 수
    private ArrayList<Bomb> parentBombs; // 이 폭탄의 폭발을 유발할 수 있는 폭탄 리스트
    Bomb(int index){
        this.index = index;
        this.childCount = 0;
        this.parentBombs = new ArrayList<>();
    }

    void addParentBombs(Bomb child){
        this.parentBombs.add(child);
        child.childCount++;
    }

    int getChildCount(){
        return childCount;
    }


    public void remove() {
        // 해당 폭탄을 제거한다
        for(int i = 0; i < parentBombs.size(); i++){
            Bomb p = parentBombs.get(i);
            p.childCount -= 1;
        }
    }

    public ArrayList<Bomb> getParentBombs() {
        return parentBombs;
    }
}