[백준] 9466번. 텀 프로젝트(JAVA)

문제

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

---

풀이

import java.io.*;
import java.util.*;

public class Main{

    static int T;
    static int check;
    static Set<Integer> team; // 팀원들의 집합
    static Stack<Integer> stack; // 팀원을 추가하기 위한 스택
    static List<Integer> list; // 임시 저장을 위한 리스트
    static int[] arr; // 학생들이 누구랑 팀원이 되고 싶은지
    static boolean[] visited; // 이미 학생을 체크했는지
    static boolean flag; // 팀 구성이 완료되었는지

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

        T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            int n =  Integer.parseInt(br.readLine()); // 새로운 학생 수 정수 n 입력 받기
            arr = new int[n]; // 배열 선언
            visited = new boolean[n]; // 방문 배열 초기화
            team = new HashSet<>(); // 팀 초기화
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                arr[j] = Integer.parseInt(st.nextToken()) - 1; // 학생 배열 초기화
            }
            for(int j = 0; j < n; j++){
                stack = new Stack<>(); // 반복시마다 스택 초기화
                list = new ArrayList<>(); // 반복 시마다 리스트 초기화
                check = -1; // 기본 체크값 -1
                dfs(j); // dfs 시작
                if(!flag){ // 팀 구성이 완료되지 않았다면
                    for(int x : list){
                        System.out.println(x);
                        visited[x] = true; // 방문 배열 초기화
                        /*
                        이렇게 해주는 이유는 무엇인가?
                        5 5 4 5 3이라는 예시를 생각해보자.
                        1번에서 5번에 대한 방문을 사이클도 못 만들었으면서 true로 바꿔버리면
                        4 -> 5 -> 3이 되지 않기 때문이다.
                        즉, 사이클을 못 만들었다면 그 값은 다시 방문할 수 있음을 확인해준다.
                         */
                    }
                    flag = false; // 플래그 초기화
                }
            }
            int answer = n - team.size(); // 학생 수 - 팀 사이즈
            sb.append(answer + "\n");
        }
        System.out.println(sb.toString());

    }

    private static void dfs(int start){
        if(visited[start]){ // 이미 방문한 곳 체크
            check = start; // 체크값을 시작 포인트로 정해줌
            /*
            예시를 들어 생각해보자.
            2 -> 3
            3 -> 4
            4 -> 2이라고 생각하면,
            처음 시작 2 -> 시작 3- > 시작4 -> 시작 2가 된다
            이 때 시작 2는 이미 true(하단 코드 참고)가 되므로 이쪽의 분기문으로 들어온다
            그럼 check = 2가 저장된다는 것이다.
            이 체크값을 사이클 확인에 사용하므로 상단 코드에서 절대 겹칠 일이 없는 -1을 기본값으로 설정해두는 것.
             */
            return;
        }

        visited[start] = true; // 방문 체크
        stack.push(start); // 스택에 집어넣음(후입선출 자료구조를 위함)
        dfs(arr[start]); // dfs 재귀 호출
        int temp = stack.pop(); // 스택의 값 뽑음
        list.add(temp); // 리스트에 넣음
        if(temp == check){ // 만약 스택에서 나온 값이 check와 같다면
            // 여기서 check 는 위의 예시라면 2고
            // stack엔 2 3 4가 들어있을 것이다. 마지막에 분기문 들어갈 때는 stack에 안 들어가므로
            team.addAll(list); // 2 3 4가 들어간 리스트를 set에 넣는다.
            flag = true; // 이 dfs에서는 사이클이 존재했음을 체크해준다.
        }

    }


}

 

사이클을 체크하려고 하는 것이다. 사이클이 완성된다면 스택에 있던 값들을 사이클의 시작지점까지만 리스트에 더한 뒤에 집합에 넣어준다. 그리고 총 학생 수에서 이를 빼주어 답을 구한다.

 

풀이는 코드에 작성했기 때문에 생략한다.

아이디어만 잘 잡을 수 있다면 코드로 구현하는 것 자체는 어렵지 않았다. 다만, 다른 분들의 코드를 확인해보니 너무 자료구조를 난잡하게 쓴 부분들이 있는 것 같다 더욱 꼼꼼하고 간결하게 코드로 구현하는 방법을 연습해야될 것 같다고 느꼈다.