백준 1005 ACM Craft Java

백준에서 가장 많이 풀린 문제 중 하나인 ACM Craft이다.

풀어본 사람이 많은 만큼 정답률도 18%로 매우 낮다.

 

나 또한 위상 정렬에 대해 공부하기 전에

풀려고 시도했다가 처참히 실패한 후 시도했지만 풀지 못한 문제에

오랫동안 묵혀있던 문제이다.

 

낮은 정답률에 비해 위상 정렬에 대해 알고 있다면 비교적 쉽게 풀 수 있는 문제이다.

위상 정렬은 DAG에서 방향성을 거스르지 않고 정점들을 나열하는 알고리즘이다.

DAG는 Direct Acyclic Graph로 사이클 없는 방향 그래프를 말한다.

위상 정렬에 관한 내용은 아래의 링크에서 친절하고 자세히 설명해 준다.

https://jason9319.tistory.com/93

 

이 문제에 적용할 위상 정렬 방법은 indegree의 수를 이용하는 방법이다.

indegree 수를 이용하는 방법은 화살표가 자신에게 향하는 수를 체크하는 방식이다.

 

위상 정렬에서 indegree수를 이용하는 방법을 공부했다면

쉽게 풀 수 있지만 내가 헷갈렸던 부분은 이 부분이다.

while(!q.isEmpty()) {
            int v = q.poll();
            for(int k : graph[v]) {
                value[k] = Math.max(value[k], value[v]+cost[k]);
                if(--in[k] == 0) {
                    q.add(k);
                }
            }
        }

여기서

value[k] = Math.max(value[k], value[v]+cost[k]);

문제의 핵심인 이 라인의 뜻을 자세히 설명하면

그림처럼 방향 그래프가 되어있다면 4는 자신에게 향하는 화살표가 2개이다.

그렇다면 정점 v에 2가 들어갔다면 k는 4가 되고 value[4]는 value[k] = value[v]+cost[k]로

21로 초기화됐을 것이다. 그리고 다음 정점 3이 들어갔다면 이번에도 k는 4가 된다.

그렇다면 value[k]는 현재 21이고 value[v]+cost[k]는 120으로 정답인 120이 value[4]에

저장되게 된다. 이 처럼 자신에게 향하는 화살표가 2개 이상인 경우를 대비해서

value[k] = Math.max(value[k], value[v]+cost[k])로 코드를 짠 것이다.

 

위상 정렬을 활용한 다른 문제들도 풀어보며 위상 정렬을 내 것으로 만들어야겠다.

 

import java.io.*;
import java.util.*;
 
public class Q1005 {
    public static int target; // 승리 위한 건물 번호
    public static int [] cost; //건물당 지어지는 ㅣ간
    public static int [] in; //들어오는 간선 수
    public static int [] value; // 앞의 건물을 포함한 지어지는 총 
    
    public static int topologicalSort(List<Integer>[] graph, int n) {
        Queue<Integer> q = new LinkedList<>();
        for(int i=1; i<=n; i++) {
            if(in[i] == 0) {
                q.add(i);
                value[i] = cost[i];
            }
        }
        while(!q.isEmpty()) {
            int v = q.poll();
            for(int k : graph[v]) {
                value[k] = Math.max(value[k], value[v]+cost[k]);
                if(--in[k] == 0) {
                    q.add(k);
                }
            }
        }
        return value[target];
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(reader.readLine());
        StringBuilder sb = new StringBuilder();
 
        while(tc-- > 0) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            cost = new int[n+1];
            in = new int[n+1];
            value = new int[n+1];
            List<Integer>[] graph = new ArrayList[n+1];
 
            for(int i=1; i<=n; i++) {
                graph[i] = new ArrayList<>();
            }
            st = new StringTokenizer(reader.readLine());
            for(int i=1; i<=n; i++) {
                cost[i] = Integer.parseInt(st.nextToken());
            }
            for(int i=0; i<m; i++) {
                st = new StringTokenizer(reader.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                graph[x].add(y);
                in[y]++; 
            }
            target = Integer.parseInt(reader.readLine());
            sb.append(topologicalSort(graph, n)+"\n");
        }
        System.out.print(sb.toString());
    }
}