[백준/java] 1005. ACM Craft

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

🌱 문제

🌱 풀이

• 주어진 K개의 건설순서 규칙을 토대로 인접리스트를 만들어주었다. 이때, 각 노드의 진입차수가 몇인지도 indegree배열에 저장해주었다.
• 진입차수가 0인 지점이, 탐색 시작지점이 되므로 queue에 넣어주 었고, dp를 해당 건물 건설시간으로 갱신한다.
• 인접한 노드들을 돌면서dp[next]=Math.max(dp[next], dp[cur]+time[next])와 같이 최댓값으로 업데이트 해주고, indegree값을 1감소 시켜준다.
• 중요한 것은, 다음 방문 노드를 무조건 queue에 넣는게 아니라 그 노드의 indegree가 0일때만 queue에 넣고, 탐색을 진행해야 한다. ( 이 방법이 위상정렬이다)

	for(int i=0; i<edges[cur].size(); i++) {
			int next=edges[cur].get(i);
			dp[next]=Math.max(dp[next], dp[cur]+time[next]);
			indegree[next]--;
					
			if(indegree[next]==0) //진입차수가 0인 것만 queue에 넣기 
				queue.add(next);
			}
     }

위상정렬이란?

• 순서가 정해진 작업을 수행할 때, 이 순서를 결정하는 알고리즘이다.
• 위상정렬을 적용하려면 반드시 DAG(Directed Acyclic Graph,유향 비순환 그래프)이어야 한다.
• 시작/도착점이 구분되지 않는 순환 형태일 경우 위상정렬을 적용할 수 없다.

틀렸던 이유

• 처음에는 다음 노드를 방문할 때, dp값 갱신해주고 나서 그 노드를 무조건 queue에 넣었었다.
• 답은 잘 나왔으나 메모리 초과가 났다.
• 2<=N<=1000, 1<=K<=100,000 이기 때문에 방문할 때마다 모든 노드를 queue에 넣으면, 인접노드가 많은 그래프가 주어질 경우 메모리 초과가 발생하게 된다. (조금만 많아져도 바로 메모리 초과 일듯. 정확한 복잡도는 잘 모르겠다.)

	while(!queue.isEmpty()) {
		int cur = queue.poll();
                
		for(int i=0; i<edges[cur].size(); i++) {
			int next=edges[cur].get(i);
			dp[next]=Math.max(dp[next], dp[cur]+time[next]);
			queue.add(next);
		}
	}

🌱 틀린 코드 (메모리 초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

// 1005.ACM craft 
public class Main {
	
	static int TC;
	static int N,K;
	static int time[];
	static int dp[];
	static int indegree[];
	static ArrayList<Integer> edges[];
	static int target;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TC= Integer.parseInt(br.readLine());
		
		for(int t=1; t<=TC; t++) {
			st = new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			
			time=new int[N+1];
			dp = new int[N+1];
			edges = new ArrayList[N+1];
			indegree = new int[N+1];
			st = new StringTokenizer(br.readLine());
			
//			edges[0]=new ArrayList<Integer>();
			for(int i=1; i<=N; i++) {
				edges[i]= new ArrayList<Integer>();
				time[i]=Integer.parseInt(st.nextToken());
			}
		
			
			for(int i=0; i<K; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				edges[from].add(to);
				indegree[to]++;
			}
			target=Integer.parseInt(br.readLine());
			
			Queue<Integer> queue = new ArrayDeque<Integer>();
			
			for(int i=1; i<=N; i++) {
				if(indegree[i]==0) {
					queue.add(i);
					dp[i]=time[i];
				}
			}
			
			while(!queue.isEmpty()) {
				int cur = queue.poll();
//				System.out.println("cur: "+cur);
				
				for(int i=0; i<edges[cur].size(); i++) {
					int next=edges[cur].get(i);
					dp[next]=Math.max(dp[next], dp[cur]+time[next]);
					queue.add(next);
				}
			}
			
//			for(int i=1; i<=N; i++) {
//				System.out.print(dp[i]+" ");
//			}
//			System.out.println();
			System.out.println(dp[target]);
		}
		
	}

}

🌱 정답 코드

package week14.boj_1005;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

// 1005.ACM craft 
public class Somyeong {
	
	static int TC;
	static int N,K;
	static int time[];
	static int dp[];
	static int indegree[];
	static ArrayList<Integer> edges[];
	static int target;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		TC= Integer.parseInt(br.readLine());
		
		for(int t=1; t<=TC; t++) {
			st = new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());
			K=Integer.parseInt(st.nextToken());
			 
			time=new int[N+1]; // 건설하는데 걸리는 시간 
			dp = new int[N+1];
			edges = new ArrayList[N+1];
			indegree = new int[N+1]; //진입차수 저장 
			st = new StringTokenizer(br.readLine());
			
//			edges[0]=new ArrayList<Integer>();
			for(int i=1; i<=N; i++) {
				edges[i]= new ArrayList<Integer>();
				time[i]=Integer.parseInt(st.nextToken());
			}
		
			
			for(int i=0; i<K; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				edges[from].add(to);
				indegree[to]++;
			}
			target=Integer.parseInt(br.readLine());
			
			Queue<Integer> queue = new ArrayDeque<Integer>();
			
			for(int i=1; i<=N; i++) {
				if(indegree[i]==0) {
					queue.add(i);
					dp[i]=time[i];
				}
			}
			
			while(!queue.isEmpty()) {
				int cur = queue.poll();
//				System.out.println("cur: "+cur);
				
				for(int i=0; i<edges[cur].size(); i++) {
					int next=edges[cur].get(i);
					dp[next]=Math.max(dp[next], dp[cur]+time[next]);
					indegree[next]--;
					
					if(indegree[next]==0) //진입차수가 0인 것만 queue에 넣기 
						queue.add(next);
				}
			}
			
			System.out.println(dp[target]);
		}
		
	}

}