[Java] 백준 BOJ / 9466번: 텀 프로젝트

텀 프로젝트

문제

---

문제 설명

텀 프로젝트를 수행하기 위해 팀을 짜는 문제이다.

1번부터 N번까지의 학생이 각자 원하는 사람을 선택을 하고 사이클이 생겨야 팀을 구성 할 수 있다.

이렇게 구성한 팀에서 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램이다.

---

구현

처음에는 유니온 파인드 알고리즘을 적용해서 풀려 했으나 유니온 파인드는 무방향 사이클을 판별할 때 사용하고 이번 문제에서는 방향성이 있는 그래프이고, 특히 유니온 파인드는 같은 집합에 속하는지만 확인하고, 그 사이클에 누가 포함되어있는지는 알 수 없다는 단점이 있어서 DFS 로 풀었다.

필요한 자료구조로는 학생들의 선택을 저장할 arr 배열, 방문 여부를 저장할 visited, 탐색 종료 여부를 확인할 finised 배열과 팀 구성을 몇 명 했는지 저장할 count 변수가 필요하다.

arr를 입력을 받은 후에 n까지 탐색하며 방문하지 않았다면 dfs 함수를 돌려준다.

for (int i = 1; i <= n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
}

for (int i = 1; i <= n; i++) {
	if (!visited[i])
		dfs(i);
}

DFS 함수에서는 함수 인자로 들어온 cur 에 대해서 방문처리를 해주고, 이 학생이 선택한 학생을 확인한다.

그 후에 그 다음 학생을 아직 확인하지 않았다면 해당 학생을 다시 함수에 넣어준다.
만약에 방문했지만 탐색이 끝나지 않았다면 next 부터 현재 cur 까지 사이클이 발생했다는 뜻이기 때문에, 사이클 을 확인하며 구성원 수를 증가한다.

public static void dfs(int cur) {
	visited[cur] = true;
    int next = arr[cur];

    if (!visited[next]) {
		dfs(next);
	} else if (!finished[next]) {
		for (int i = next; i != cur; i = arr[i])
			count++;
        count++;
    }
	finished[cur] = true;
}

루프에서는 cur 전까지의 학생만 셌기 때문에 마지막에 1을 더해줘야한다.

그렇게 나온 count 변수는 사이클이 발생한 모든 학생이기 때문에 처음에 입력받은 전체 학생수인 n에서 count를 빼주면 된다.

---

코드

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

public class Main_9466 {
    static int testCase;
    static int[] arr;
    static boolean[] visited, finished;
    static int n, count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());
        while (testCase-- > 0) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n + 1];

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

            StringTokenizer st = new StringTokenizer(br.readLine());

            for (int i = 1; i <= n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            for (int i = 1; i <= n; i++) {
                if (!visited[i])
                    dfs(i);
            }

            System.out.println(n - count);
        }
    }

    public static void dfs(int cur) {
        visited[cur] = true;
        int next = arr[cur];

        if (!visited[next]) {
            dfs(next);
        } else if (!finished[next]) {
            for (int i = next; i != cur; i = arr[i])
                count++;
            count++;
        }
        finished[cur] = true;
    }
}