[BOJ] 백준 9466 텀 프로젝트

출처:  https://www.acmicpc.net/problem/9466

 Input 

2

7

3 1 3 7 3 4 6

8

1 2 3 4 5 6 7 8

 

 Output 

3

0

Test Case #1의 경우 아래와 같이 배열을 표현.

　

사이클을 형성하는 정점은 {4, 7, 6}, {3}으로

사이클을 속하지 못한 정점은 3개 입니다.

* 정점 1개로 사이클을 형성할 수 있음

※ 사이클을 형성하는 정점은 사이클끼리 간선을 가지는 형태

 

※ 위상정렬 (Topological sort)  

위상정렬 (Topological sort)

 

구현

* DFS를 통해 연결된 정점을 순회하되 사이클 형성 여부를 파악하기 위해서는

   탐색을 시작한 지점에 대한 재방문이 필요.

① 방문하지 않은 정점을 시작 정점으로 해서 DFS 탐색

② checked[] : 이전 DFS 탐색 통해 사이클 가능 여부를 판단이 끝난 정점

③ visitied[] : DFS 탐색이 끝나는 시점을 알기 위한 사이클이 형성 여부

                      (사이클의 시작과 끝 위치)

 

시뮬레이션

낮은 번호의 정점 [1] 노드부터 DFS 탐색

DFS: [1 → 3 → 8 → 3] 탐색으로 3을 중복방문(visitied[])

▶ {3, 8} 사이클 형성

    * 처음 [3]을 방문 했던 시점에서 재방문 전 [8]까지 사이클을 형성

아직 탐색하지 않은 [2] DFS 탐색

DFS: [2 → 1] 이미 탐색이 끝난(checked[]) [1]정점 방문.

정점 [1]이 사이클을 형성 여부와 상관없이 정점 [2]는 사이클을 형성 못함 

이는 [9] 노드가 [1]을 방문할때도 마찬가지. 

*인접 리스트를 활용해서 방향 그래프 구현

  한 정점에서 나가는 방향의 개수가 1개이므로 인접리스트가 효율적.

  인접행렬의 개수 N x N 크기의 불필요한 메모리 차지

 

 Input 

1

5

5 3 4 5 1

 

 Output 

3

 

※ 같이 보면 좋은 문제: [BOJ] 10451 순열 사이클 

[BOJ] 백준 10451 순열 사이클

---

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    
    static ArrayList<ArrayList<Integer>> adList;
    static boolean[] visitied, checked;
    static Stack<Integer> stack;
    static int answer;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.next());
        
        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(sc.next());
            
            adList = new ArrayList<>();
            // arrayList 구조상 시작인덱스는 0이므로 dummy data로 한개 넣는다.
            adList.add(new ArrayList<>());
            
            // 1~N까지의 시작 노드를 adList에 넣는다.
            for(int j=1; j<=N; j++) {
                adList.add(new ArrayList<>());
                
                // 문제에서 입력한 노드 연결을 입력 받는다.
                int target = Integer.parseInt(sc.next());
                // 방금 넣은 노드의 연결하고자 대상이 된다.
                adList.get(j).add(target);
            }
            visitied = new boolean[N+1];
            checked = new boolean[N+1];
            stack = new Stack<>();
            answer = 0;
            
            for(int j=1; j<=N; j++) {
                // 방문한적이 있는 곳이라면 이미 팀 판단여부가 끝났다면 pass
                // visitied[]는 매 DFS마다 초기화되서 시작하게 해놓았다.
                if(checked[j]) {
                    continue;
                }
                // 스택 비워주기
                stack.clear();
                DFS(j);
            }
            // 정답출력
            System.out.println(answer);
        }
    }
    
    private static void DFS(int curPosition) {
        // 이미 싸이클이 확인된 지점과 선택(희망)한다면 그동안 쌓인 경로들을 팀을 형성할 수 없는
        // 헛된 희망을 하고 있는 곳이므로 결과값에 합한다.
        if(checked[curPosition]) {
            answer += stack.size();
            // 팀 가능 여부를 불가능으로 끝났다고 표시
            for(int i=0; i<stack.size(); i++) {
                checked[stack.get(i)] = true;
            }
            return;
        }
        // checked[curPosition]=fasle이면서
        // 이미 방문한 곳에 도달 했다면 싸이클이 형성이 어디구간인지 확인해야 한다.
        if(visitied[curPosition]) {
            // 우선 팀 가능여부 판단이 끝났으므로 체크한다.
            for(int i=0; i<stack.size(); i++) {
                checked[stack.get(i)] = true;
            }
            // 싸이클을 형성하고 있는 원소를 무엇인지 구하는 것이 아니므로 개수만 파악한다.
            // 스택에서 일일이 찾기보다는 map형태로 바로 찾는 것도 좋은 방법일 것이다.
            for(int i=0; i<stack.size(); i++) {
                if(stack.get(i) == curPosition) {
                    answer += i;
                    return;
                }
            }
        }
        
        // DFS 진행의 방문표시
        visitied[curPosition] = true;
        // 사이클 경로를 알기위한 방문한 노드 저장
        stack.push(curPosition);
        DFS(adList.get(curPosition).get(0));
        // 다음 DFS 탐색을 위해 초기화 해놓음
        visitied[curPosition] = false;
    }
}