728x90
https://www.acmicpc.net/problem/20119
메모리: 148,628 KB , 시간: 1,356 ms
사용 알고리즘: 방향 비순환 그래프, 그래프 이론, 그래프 탐색, 위상 정렬
728x90
기존의 위상 정렬은
앞서 실행되어야 하는 노드들의 목록이 하나였는데,
이 문제에서는 하나의 물약을 만들 수 있는 레시피들이 여러 개가 있을 수 있다.
이를 고려해주어야 해서 좀 까다로운 문제인 것 같다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; ArrayList<Integer> resultList = new ArrayList<>(); // 만들 수 있는 물약 리스트(답 리스트) st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); // 위상 정렬 // edges.get(i) := i번 물약을 재료로 가지고 있는 물약 리스트 // edges.get(i).get(j) -> {a, b} := a번 물약의 b번 레시피에서 i번 물약을 재료로 사용함 ArrayList<ArrayList<int[]>> edges = new ArrayList<>(); for (int i = 0; i <= N; i++) { edges.add(new ArrayList<>()); } // count.get(i) := i번 물약을 만들기 위해 필요한 레시피별 물약 개수 ArrayList<ArrayList<Integer>> count = new ArrayList<>(); for (int i = 0; i <= N; i++) { count.add(new ArrayList<>()); } Queue<Integer> q = new ArrayDeque<>(); int k, r, index; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); k = Integer.parseInt(st.nextToken()); for (int j = 0; j < k; j++) { q.offer(Integer.parseInt(st.nextToken())); } r = Integer.parseInt(st.nextToken()); // 재료 물약들에게 r번 물약 index번 레시피 재료로 사용된다고 알려줌 index = count.get(r).size(); while(!q.isEmpty()) { edges.get(q.poll()).add(new int[] {r, index}); } count.get(r).add(k); // r번 물약의 index번 레시피에 k개의 재료 물약이 필요함 } int L = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); int tmp; for (int i = 0; i < L; i++) { tmp = Integer.parseInt(st.nextToken()); q.add(tmp); // 이미 가지고 있는 물약 count.get(tmp).clear(); // 이미 가지고 있으므로, 이 물약을 만들기 위해 더 이상 재료가 필요하지 않음 resultList.add(tmp); // 답 리스트에 넣음 } int now; int[] next; ArrayList<int[]> edge; while(!q.isEmpty()) { now = q.poll(); // 이미 가지고 있거나, 만들 수 있는 물약 edge = edges.get(now); // now번 물약을 재료로 사용하는 레시피 리스트 for (int i = 0; i < edge.size(); i++) { next = edge.get(i); // 이미 가지고 있거나 만들 수 있는 물약이면 넘어감 if(count.get(next[0]).isEmpty()) continue; tmp = count.get(next[0]).get(next[1]); // next[0]번 물약의 next[1]번 레시피에 필요한 재료 물약 개수 if(tmp == 1) { // 필요한 재료 물약을 모두 가지게 되었음 q.add(next[0]); count.get(next[0]).clear(); resultList.add(next[0]); } else { // 아직 재료가 더 필요하면, 필요한 재료 개수만 줄여줌 count.get(next[0]).set(next[1], tmp - 1); } } } Collections.sort(resultList); // 답 리스트 정렬 // 출력 StringBuilder result = new StringBuilder(); result.append(resultList.size()).append("\n"); for (int i = 0; i < resultList.size(); i++) { result.append(resultList.get(i)).append(" "); } System.out.println(result); } }
728x90
'Problem Solving > BOJ' 카테고리의 다른 글
[백준, BOJ 18430] 무기 공학 (java) (0) | 2024.10.15 |
---|---|
[백준, BOJ 20291] 파일 정리 (java) (0) | 2024.10.15 |
[백준, BOJ 1439] 뒤집기 (java) (0) | 2024.10.14 |
[백준, BOJ 10825] 국영수 (java) (1) | 2024.10.12 |
[백준, BOJ 10282] 해킹 (java) (0) | 2024.10.11 |