[BOJ] 백준 [4013] ATM JAVA

https://www.acmicpc.net/problem/4013

4013번: ATM

[문제]

 

[풀이]

어우 .. 어질어질하다..
SCC 활용 DP 문제이긴 한데 , 처음에 SCC 집단들을 구해서 indegree가 0인거부터 진행했는데 왜 안되지..? 했다가
나중에 알고보니 start 지점이 정해져있다는 걸 뒤늦게 알았고 한참을 헤맸다 ..

접근방법
1. SCC집단을 구할 것.
2. SCC집단마다 번호를 매기고 , 이 자체를 하나의 Node로 취급하여 또 다른 totalATM을 만들어서 atm의 합을 구함.
3. start 지점의 SCC부터 탐색을 진행해서 totalATM을 더해나가는 DP를 갱신시킴
4. SCC 지점이 레스토랑이면 DP 값들 중 최대값을 구해서 리턴

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
public class Main {
    static boolean[] finished,isRes;
    static int n, m, index, sccIndex, start, max;
    static int[] discover,sccNum,atm,totalAtm,dp;
    static ArrayList<ArrayList<Integer>> list,sccList;
    static Stack<Integer> st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        list = new ArrayList<>();
        atm = new int[n+1];
        for (int i = 0; i <= n; i++) list.add(new ArrayList<>());
 
        for (int i = 0; i < m; i++) {
            int[] edge = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            list.get(edge[0]).add(edge[1]);
        }
        for(int i=1;i<=n;i++) atm[i] = Integer.parseInt(br.readLine());
 
        input = br.readLine().split(" ");
        start = Integer.parseInt(input[0]);
        isRes = new boolean[n+1];
        Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).forEach(e->isRes[e]=true);
 
        findScc();
        setSccInfo();
        sccBfs();
 
        for(int i=1;i<=n;i++)
            if(isRes[i]) max = Math.max(max,dp[sccNum[i]]);
        System.out.println(max);
 
    }
 
    private static void sccBfs() {
        LinkedList<Integer> q = new LinkedList<>();
        q.add(sccNum[start]);
        dp[sccNum[start]] = totalAtm[sccNum[start]];
 
        while (!q.isEmpty()){
            Integer cur = q.poll();
 
            for (Integer next : sccList.get(cur)) {
                if(dp[next] < dp[cur] + totalAtm[next]){
                    dp[next] = dp[cur]+totalAtm[next];
                    q.add(next);
                }
            }
        }
    }
 
 
    private static void setSccInfo() {
        totalAtm = new int[sccIndex+1];
        sccList = new ArrayList<>();
        dp = new int[sccIndex+1];
        for(int i=0;i<=sccIndex;i++) sccList.add(new ArrayList<>());
 
        for (int i = 1; i <= n; i++) {
            totalAtm[sccNum[i]]+=atm[i];
            for (Integer next : list.get(i))
                if (sccNum[i] != sccNum[next]) sccList.get(sccNum[i]).add(sccNum[next]);
        }
    }
 
    private static void findScc() {
 
        index = 0;
        discover = new int[n + 1];
        finished = new boolean[n + 1];
        st = new Stack<>();
        sccIndex = 0;
        sccNum = new int[n + 1];
 
        for (int i = 1; i <= n; i++)
            if (discover[i] == 0) dfs(i);
 
    }
 
    private static int dfs(int cur) {
        discover[cur] = ++index;
        st.push(cur);
 
        int parent = discover[cur];
        for (Integer next : list.get(cur)) {
            if (discover[next] == 0) parent = Math.min(dfs(next), parent);
            else if (!finished[next]) parent = Math.min(discover[next], parent);
        }
 
        if (parent == discover[cur]) {
            while (true) {
                Integer pop = st.pop();
                finished[pop] = true;
                sccNum[pop] = sccIndex + 1;
                if (pop == cur) break;
            }
            sccIndex++;
        }
        return parent;
    }
}