[백준 2637] 장난감조립 (Java)

문제 링크: https://www.acmicpc.net/problem/2637

2637번: 장난감조립

1. 주의할 점

- 위상정렬로 접근한다

- 필요한 물품의 개수를 List 형태로 담지 않는다 → 메모리 초과 회피

 

2. 구현

- Info 형태의 구조체를 이용하여 A의 물건을 만들기 위해 Idx번째 물건이 Val만큼 필요하다는 것을 나타낸다

- Need[] 배열을 통해 필요한 총 물건의 수를 저장한다

- Conn[] 배열을 통해 연결된 상위부품의 수를 나타낸다

- isElement[] 배열을 통해 기본 부품인지 나타낸다

- 모든 변수들을 초기화하고 시작한다

- 역 위상정렬을 사용하여 A가 만들어지기 위해 B번째 부품 Val개가 필요하다는 것을 Li[A]에 저장한다

- 완제품부터 역으로 시작하여 LI[]를 통해 필요한 기본부품을 Need[] 배열에 나타낸다

 

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

class Main {
    static class Info{
        int idx,val;
        public Info(int idx, int val){
            this.idx = idx;
            this.val = val;
        }
    }
    
    static int need[],conn[];
    static boolean isElement[];
    static int node,query,result;
    static List<Info> li[];
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    result=0;
	    need = new int[node+1];
	    conn = new int[node+1];
	    isElement = new boolean[node+1];
	    li = new List[node+1];
	    for(int i=1;i<=node;i++){
	        li[i] = new ArrayList<>();
	        isElement[i]=true;
	    }
	    
	    str = br.readLine();
	    st = new StringTokenizer(str);
	    query = Integer.parseInt(st.nextToken());
	    
	    for(int i=0;i<query;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int a = Integer.parseInt(st.nextToken());
	        int b = Integer.parseInt(st.nextToken());
	        int val = Integer.parseInt(st.nextToken());
	        conn[b]++;
	        li[a].add(new Info(b,val));
	        isElement[a]=false;
	    }
	    Queue<Integer> q = new LinkedList<>();
	    q.offer(node);
	    need[node]=1;
	    while(!q.isEmpty()){
	        int cidx = q.poll();
	        int cv = need[cidx];
	        for(int i=0;i<li[cidx].size();i++){
	            int next = li[cidx].get(i).idx;
	            int nv = li[cidx].get(i).val;
	            conn[next]--;
	            need[next]+=(cv*nv);
	            if(conn[next]==0) q.offer(next);
	        }
	    }
	    for(int i=1;i<=node;i++){
	        if(isElement[i]==true){
	            System.out.println(i+" "+need[i]);
	        }
	    }
	}
}