[백준 Java]9466_텀프로젝트

[문제 링크] 9466 텀 프로젝트 자바 백준 

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

9466번: 텀 프로젝트

[생각 흐름]

처음에는 for문으로 i에서 모든 경로를 확인하여 사이클을 확인하려 하였는데 시간 초과가 났다.

그래서 O(n)으로 통과할 수 있는 방법을 찾다가 i번째부터 연결된 경로를  따라가다가 사이클이 생기면 처리하는 방식으로 해결하였다.

1)  1->2->3->4->2 와같은 상황이라면 사이클이 생겨서 2번 사람의 전 사람은 혼자 해야 한다.
 각 노드를 링크를 따라가면서 숫자 번호를 부여한다. 이경우에는 이번턴에 해당하는 사람이 한번 더 나온 경우로  2의 값에서 -1을 하여 1을 더하면 된다. (이번 턴에 나온 지 확인하기 위해 nowturn에 확인하는 값을 넣고 확인하였다.) 

2)  vistit[3]의 값이 채워진 상태에서 5 -> 6 -> 3과 같은 상황이 있다면 이번 턴에 해당하는 사람(5, 6)을 모두 저장하고 있다가 만약  visit이 채워진 경우라면 앞의 사람들은 모두 혼자 해야 하므로  now(지금까지 몇 번째 가리켜서 왔는지)를 더하였다.[[2번 풀이]]

 

즉, 0~i까지 돌면서 현재 방문 노드가 이전에 방문되지 않았다면 들어가서 사이클이 있는지 확인하여 사이클이 있다면 사이클이 이루어지지 않은 경우만 체크하여 더하고, 사이클이 없는데 만약 이전에 방문이 된 노드라면 그 전까지의 사람들은 모두 혼자 해야 하므로 더하는 방식으로 계산하였다.

 

하지만 위상정렬을 이용하면 더 쉽게 풀이가 가능하다. [[1번 풀이]]

위상 정렬에서는 indegree에서 자신의 노드를 가리킨 사람의 수를 말한다(이 경우에는 자신과 팀을 하고 싶다고 가리킨 경우이다)

위 문제에서 팀을 이루기 위해서는 나가는 노드와 자신을 가리키는 노드가 하나여야 사이클이 이루어질 수 있는 조건을 만족한다.

따라서 만약 indegree가 0이라면 자신을 가르키는 노드가 없으므로 혼자 게임을 해야 하므로 사이클이 이루어질 수 없다.

또한 만약 indegree가 0인 노드를 제거하여서 연속된 노드의 indegree가 0이 된다면 그 사람 또한 사이클이 이루어지는 조건을 충족하지 못하므로 혼자 해야 한다. (사이클이 이루어지는 경우는 indegree가 0이 될 수 없다.) 

따라서 indegree가 0이되면 cnt를 증가시키는 방식으로 구현할 수 있다.

 

[코드 1]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static ArrayList<ArrayList<Integer>> graphs = new ArrayList<>();
    private static int indegree[];

    private static int toopologySort() {
        int cnt =0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0){
                queue.add(i);
                cnt++;
            }
        }

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int next : graphs.get(now)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    cnt++;
                    queue.add(next);
                }
            }
        }
        return cnt;
    }

    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) {
            graphs.clear();
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            indegree = new int[n];
            for (int i = 0; i < n; i++) graphs.add(new ArrayList<Integer>());
            for (int i = 0; i < n; i++) {
                int s = i;
                int e =Integer.parseInt(st.nextToken()) - 1;
                indegree[e]++;
                graphs.get(s).add(e);
            }
            sb.append(toopologySort()).append("\n");
        }
        System.out.println(sb);
    }

}

 

 

[코드 2]

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;
        StringBuilder sb = new StringBuilder();

        int TC = Integer.parseInt(br.readLine());
        while(TC --> 0){
            int num = Integer.parseInt(br.readLine()); //사람 수
            int array[]= new int[num+1]; //인풋 값
            int visited[] = new int[num+1]; //방문하였는지
            int alone = 0; //혼자 해야한는 사람

            st = new StringTokenizer(br.readLine());
            for(int j=1;j<=num;j++) {
                array[j]=Integer.parseInt(st.nextToken());
            }


            for(int i=1;i<=num;i++){
                if(visited[i]!=0)continue; //이미 방문함
                Queue<Integer> q = new LinkedList<>(); // 변수로 선언해도 가능
                ArrayList<Integer> nowturn = new ArrayList<>(); //이번턴에 돌았는지 확인하기 위해서
                q.add(i); //i번부터 시작
                int now = 1; // 몇번째 위치인지 확인하기 위해서 
                visited[i]=now++; //i번 노드에 몇번째에 방문했는지
                nowturn.add(i); //이번턴에 돈 노드에 추가

                while(!q.isEmpty()){
                    int a = q.poll();

                    int next = array[a];//a가 가르킨 다음사람
                    if(visited[next]!=0){ //만약 가르킨 사람이 이미 방문했던 사람이라면 
                        if(!nowturn.contains(next))alone += visited[a]; //이번턴에 방문한 사람이 아니라면(이전까지는 전부다 혼자 해야함)
                        else alone += visited[next]-1; //이번턴에 방문한 사람이므로 가르킨 사람전까지는 혼자 해야함 
                        break;
                    }
                    nowturn.add(next);
                    visited[next]=now++;
                    q.add(next);
                }
            }
            sb.append(alone).append("\n");
        }
        System.out.println(sb);
    }
}