[Java] 폭탄제거 순서정하기

1. 문제설명

폭탄 제거 문제 << 이 문제에서 폭탄의 폭발 여부만 판단했다면 이 문제는 해제순서를 출력
단, 해제 방법이 여러방법이라면 작은 번호부터 제거

2. 알고리즘 접근

1 -> 2 -> 3 -> 4 -> 5
6 -> 7
위와 같은 방식일 때 우리가 전에 푼 방식이라면 큐에 해제할 수 있는 폭탄을 추가하고
5, 7
폭탄을 해제하면 그 다음에 해제할 수 있는 폭탄을 큐에 또 넣었다
5(해제), 7, 4 << 이 방식만 봐도 순서가 5, 7, 4 이렇게 된다
그렇다면 7은 그냥 놔두고 5, 4, 3, 2, 1 이렇게 해제 하고 7, 6을 해제하는 식으로 접근

우선순위 큐 Priority Queue

여러 데이터들 중 가장 우선순위가 높은 데이터에 대한 빠른 갱신, 접근

• 비교 가능한 데이터는 자유롭게 추가 가능
• 접근/삭제가 가능한 원소는 '저장된 전체 데이터 중' 가장 우선순위가 높은 데이터
• Heap구조로 구현 (ArrayList, 배열로도 heap구현 가능)
• N개의 데이터를 차례로 삽입 후, 차례로 pop하면 정렬된 상태로 꺼낼 수 있다.

즉 큐의 최소값을 우선순위로 설정하여 문제를 풀이한다

3. 소스코드

import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);
	public static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

	public static ArrayList<Bomb> getRemovableOrders(int n, Bomb[] bombs) {
		ArrayList<Bomb> removedList = new ArrayList<>();

		// poll시에 제거 가능한 폭탄들 중 가장 인덱스가 작은 번호가 반환될 수 있도록
		// PriorityQueue를 사용한다. 폭탄들의 우선순의는 compareTo 메소드로 정의했다.
		PriorityQueue<Bomb> removableBombs = new PriorityQueue<>();
		
		for(int i = 0; i < n; i ++){
			if(bombs[i].getChildCount() == 0){
				removableBombs.add(bombs[i]);
			}
		}
		while(removableBombs.isEmpty() == false){
			Bomb b = removableBombs.poll();
			b.remove(); 
			removedList.add(b);
			
			ArrayList<Bomb> parents = b.getParentBombs();
			for(int i = 0; i < parents.size(); i++){
				Bomb p = parents.get(i);
				if(p.getChildCount() == 0){
					removableBombs.add(p);
				}
			}
			
		}

		// 모든 폭탄이 제거되지 않았다면 null을 반환한다.
		if (removedList.size() != n) {
			return null;
		}
		return removedList;
	}

	public static void testCase(int caseIndex) throws Exception {
		int n = scanner.nextInt();
		int m = scanner.nextInt();

		Bomb[] bombs = new Bomb[n];
		for (int i = 0; i < n; i += 1) {
			bombs[i] = new Bomb(i);
		}

		for (int i = 0; i < m; i++) {
			int u = scanner.nextInt() - 1;
			int v = scanner.nextInt() - 1;
			Bomb parent = bombs[u];
			Bomb child = bombs[v];

			child.addParentBombs(parent);
		}

		ArrayList<Bomb> orders = getRemovableOrders(n, bombs);

		if (orders == null) {
			writer.write("NO\n");
		} else {
			for (int i = 0; i < n; i++) {
				Bomb b = orders.get(i);

				if (i > 0) {
					writer.write(" ");
				}
				writer.write(String.valueOf(b.index + 1));
			}
			writer.write("\n");
		}
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}

		writer.flush();
		writer.close();
	}

}

class Bomb implements Comparable<Bomb> {
	public final int index;

	private int childCount;
	private ArrayList<Bomb> parentBombs;

	Bomb(int index) {
		this.index = index;
		this.parentBombs = new ArrayList<>();
		this.childCount = 0;
	}

	public void addParentBombs(Bomb parentBomb) {
		this.parentBombs.add(parentBomb);
		parentBomb.childCount += 1;
	}

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

	public int getChildCount() {
		return childCount;
	}

	public void remove() {
		for (int i = 0; i < parentBombs.size(); i += 1) {
			Bomb p = parentBombs.get(i);
			p.childCount -= 1;
		}
	}

	@Override
	public int compareTo(Bomb o) {
		// 인덱스가 작을수록 priorityQueue에서 먼저 poll 되도록
		// 우선순위를 정의한다.
		return this.index - o.index;
	}
}

사실 이전의 코드에서 우선순위만 정해주면 되는 문제