백준 1005 - ACM Craft

[문제 바로가기]

 

1. 유형

위상 정렬, 동적 프로그래밍

 

2. 문제 접근

2-1. 설계

기본적인 위상 정렬 템플릿을 사용하고, 거기다가 DP를 추가한 문제입니다.

 

 

 

2-2. 풀이법

1. 가장 처음에 차수(해당 노드에 들어 노는 선분 수)를 초기화합니다.

2. 차수가 0인 것만 큐에 넣습니다

3. 큐에서 하나씩 꺼내면서 연결된 노드를 탐색합니다. 그리고 차수를 하나씩 감소시키고, 해당 노드까지의 누적 가중치를 갱신합니다.

   3-1. 만약 차수가 0이 되면 큐에 집어넣습니다.

4. 3번을 큐가 빌 때까지 반복합니다.

 

끝.

 

3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = stoi(st.nextToken());
		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			int N = stoi(st.nextToken());
			int M = stoi(st.nextToken());
			int val[] = new int[N + 1];//가중치
			int cnt[] = new int[N+1];//각 노드마다 들어오는 차수
			int dp[] = new int[N+1];//누적 최대값
			List<Integer> list[] = new ArrayList[N + 1];
			for (int i = 0; i <= N; i++) {
				list[i] = new ArrayList<>();
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; i++) {
				val[i] = stoi(st.nextToken());
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int a = stoi(st.nextToken());
				int b = stoi(st.nextToken());
				list[a].add(b);
				cnt[b]++;
			}
			st = new StringTokenizer(br.readLine());
			int K = stoi(st.nextToken());
			//위상정렬 시작
			Queue<Integer> q= new LinkedList<>();
			for(int i=1; i<=N; i++) {
				if(cnt[i]==0) {
					q.add(i);
					dp[i] = val[i];
				}
			}
			while(!q.isEmpty()) {
				int cur = q.poll();
				for(int next: list[cur]) {
					cnt[next]--;
					dp[next] = Math.max(val[next]+dp[cur], dp[next]);
					if(cnt[next]==0) {
						q.add(next);
					}
				}
			}
			System.out.println(dp[K]);
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}