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

 

 

 

문제 출저

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

9466번: 텀 프로젝트

 

 

문제 풀이

학생들과 학생들이 선호하는 학생이 1차원 배열로 주어집니다.

이 때 서로를 가리키다 사이클이 완성되면 팀을 이루게 됩니다.

팀을 이루지 못한 학생들이 몇 명인지 구하는게 문제의 요구사항입니다.

 

dfs와 방문 처리로 문제를 풀었습니다. 

visited와 finished라는 boolean 배열을 만들었습니다.

visited : 사이클을 이루는 구성원인지 판단

finished : 이미 탐색을 마친 학생 여부 저장 

 

finished를 이용해 중복 탐색을 방지하여 시간 초과를 피하여 문제를 풀 수 있었습니다. 

 

 

소스 코드 

package baekjoon.backjoon10.day2131.day23;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


/*
텀 프로젝트
https://www.acmicpc.net/problem/9466
 */
public class B9466 {

    static int t;
    static int n;
    static int[] board;
    static StringBuilder sb;

    static boolean[] visited; // 방문 여부 확인
    static boolean[] finished; // 탐색 완료
    static int result;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());

        sb = new StringBuilder();

        for(int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());
            board = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j < n+1; j++) {
                board[j] = Integer.parseInt(st.nextToken());
            }
            simulation();
        }

        System.out.println(sb.toString());

    }


    public static void simulation() {

        visited = new boolean[n+1];
        finished = new boolean[n+1];
        result = 0;

        for(int i = 1; i < n+1; i++) {
            if(finished[i] == false) {
                search(i);
            }
        }



        sb.append(n-result).append("\n");

    }

    // 순환을 찾는 메소드
    // finished를 통해 중복 탐색 예방
    // 순환을 찾으면 다시 순환을 돌면서 result+1, finished 를 true 처리
    // finished가 true 이므로 순환을 마치고 나옴
    public static void search(int number) {

        if(finished[number] == true) {
            return;
        }

        if(visited[number]) {
            finished[number] = true;
            result++;
        }

        visited[number] = true;
        search(board[number]);


        finished[number] = true;
        visited[number] = false;

    }
}