[BOJ] 백준 [2152] 여행계획세우기 JAVA

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

2152번: 여행 계획 세우기

[문제]

[풀이]

SCC + DP 문제이다.

최대한 많이 여행하기 위해선 왔던곳을 경로만 있다면 몇번이든 돌아다녀서 최종적으로 얼마나 돌아다녔는지를 구해야한다.

1. SCC 생성
  SCC를 이루고 있는 도시들을 하나의 큰 Node로 취급하는 SCC를 여러개 만들어준다.
2. SCC 그래프 연결
  SCC Node 끼리 그래프를 형성하는데 , 이 때 가중치를 그 SCC안의 도시 갯수의 총 합으로 설정한다.
3. 탐색
  시작지점의 SCC 번호에서 부터 출발하여, 최장거리 다익스트라를 실행해서 dp[끝지점] 을 반환한다.

처음엔 그냥 SCC그래프를 탐색했더니 메모리 초과가났다.
다익스트라로 2번과 3번과정을 수정하여 AC를 받았음. 

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
 
public class Main {
 
    static Stack<Integer> st;
    static ArrayList<ArrayList<Integer>> map;
    static ArrayList<int[]>[] sccGraph;
    static int n,start,end,index,sccIndex;
    static int[] discover,sccNum,sccCount;
    static boolean[] finish;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        start = input[2]; end = input[3];
        n = input[0];
        map = new ArrayList<>();
        for(int i=0;i<=n;i++) map.add(new ArrayList<>());
        for(int i=0;i<input[1];i++){
            int[] edge = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            map.get(edge[0]).add(edge[1]);
        }
        setScc();
        int result = getCityCount();
        System.out.println(result);
    }
    static int getCityCount(){
 
        sccGraph = new ArrayList[sccIndex+1];
        for(int i=1;i<=sccIndex;i++) sccGraph[i] = new ArrayList<>();
 
        for(int i=1;i<=n;i++)
            for (Integer next : map.get(i))
                if (sccNum[i] != sccNum[next])
                    sccGraph[sccNum[i]].add(new int[]{sccNum[next],sccCount[sccNum[next]]});
 
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o2[1]-o1[1]);
        q.add(new int[]{sccNum[start],sccCount[sccNum[start]]});
        int[] dp = new int[sccIndex+1];
        dp[sccNum[start]] = sccCount[sccNum[start]];
        int result = 0;
        while (!q.isEmpty()){
            int[] cur = q.poll();
            if(cur[1] < dp[cur[0]]) continue;
            for (int[] next : sccGraph[cur[0]]) {
                if(dp[next[0]] < dp[cur[0]]+next[1]){
                    dp[next[0]] = dp[cur[0]]+next[1];
                    q.add(new int[]{next[0],dp[next[0]]});
                }
            }
        }
 
        return dp[sccNum[end]];
    }
    static void setScc(){
        st = new Stack<>();
        discover = new int[n+1];
        finish = new boolean[n+1];
        sccNum = new int[n+1];
        sccCount = new int[n+1];
        index=0;sccIndex=0;
 
        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 : map.get(cur)) {
            if(discover[next]==0) parent = Math.min(dfs(next),parent);
            else if(!finish[next]) parent = Math.min(discover[next],parent);
        }
 
        if(parent==discover[cur]){
 
            int cnt=0;
            while (true){
                Integer pop = st.pop();
                finish[pop]=true;
                sccNum[pop] = sccIndex+1; // 해당 Node가 어느 scc에 속하는지 기록
                cnt++;
                if(pop==cur) break;
            }
            sccCount[sccIndex+1] = cnt; //sccIndex에 몇개의 scc가 있는지 기록
            sccIndex++;
        }
        return parent;
    }
}