[BOJ] 백준 [3977] 축구전술 JAVA

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

3977번: 축구 전술

문제

 

풀이

이동 구간 경로가 주어 졌을 때 , 어느쪽을 스타트로 잡아야 하는지 정하는 문제다.

첫 번째 입력을 그래프로 나타내면 다음과 같은데 
만약 3번에서 시작한다고 하면 주어진 경로를 모두 탐색할 수 없기 때문에 불가능.

그럼 나머지 0,1,2 번 지점에서는 저 중 아무곳에서 출발을 해도 모든 구간을 탐색이 가능하기 때문에 0,1,2 가 답.
즉 , { 0, 1, 2 } 를 하나의 큰 노드로 보고 Indegree = 0 인 구간에서 시작하면 된다는 뜻.

따라서 { 0, 1, 2 } 를 하나의 큰 노드로 보기위해 SCC 알고리즘을 사용해야 한다.
하지만 반례도 있다.

두 번째 입력 예제에선 1번과 2번노드 둘다 indegree=0 이 되기 때문에 서로 간에 이동이 불가능하다.
따라서 SCC 를 구한 후 , Indegree=0 인경우를 카운팅하여 2개 이상인 경우엔 예외로 처리하면 끝

import java.util.*;
import java.io.*;
import java.util.stream.*;
 
import static java.util.Arrays.*;
 
public class Main {
 
    static int index,sccCount;
    static int[] discover,finish,sccNum,inDegree;
    static ArrayList<ArrayList<Integer>> graph;
    static Stack<Integer> st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while (tc-->0){
            graph = new ArrayList<>();
            int[] input = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            for(int i=0;i<input[0];i++) graph.add(new ArrayList<>());
            for(int i=0;i<input[1];i++){
                int[] edge = stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
                graph.get(edge[0]).add(edge[1]);
            }
            findScc();
            setIndegree();
            String ans = getStartPoint();
            System.out.println(ans);
            br.readLine();
        }
    }
 
    static void findScc(){
 
        st = new Stack<>();
        index=0; sccCount=0;
        finish = new int[graph.size()];
        discover = new int[graph.size()];
        sccNum = new int[graph.size()];
 
        for(int i=0;i<graph.size();i++)
            if(discover[i]==0) dfs(i);
    }
 
    private static void setIndegree() {
        inDegree = new int[sccCount+1];
        for(int i=0;i<graph.size();i++) {
            for (Integer next : graph.get(i))
                if (sccNum[next] != sccNum[i]) inDegree[sccNum[next]]++;
        }
    }
 
    private static String getStartPoint() {
        int zeroCount=0;
        ArrayList<Integer> sccList = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<inDegree.length;i++){
            if(inDegree[i]==0 && zeroCount==0){
                zeroCount++;
                for(int j=0;j<sccNum.length;j++)
                    if(i==sccNum[j]) sccList.add(j);
            }else if(inDegree[i]==0 && zeroCount!=0){
                sb.append("Confused").append("\n");
                return sb.toString();
            }
        }
        Collections.sort(sccList);
        sccList.forEach(e->sb.append(e).append("\n"));
        return sb.toString();
    }
 
    private static int dfs(int cur) {
 
        discover[cur] = ++index;
        st.push(cur);
 
        int parent = discover[cur];
 
        for (Integer next : graph.get(cur)) {
 
            if(discover[next]==0) parent = Math.min(parent,dfs(next));
            else if(finish[next]==0) parent = Math.min(parent,discover[next]);
        }
        if(parent == discover[cur]){
            while (true){
                Integer pop = st.pop();
                finish[pop]=1;
                sccNum[pop] = sccCount+1;
                if(pop==cur) break;
            }sccCount++;
        }
        return parent;
    }
}