[알고리즘 / 백준] 9466 - 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

문제는 위와 같으며, BFS 를 통해 문제를 풀 수 있습니다.

 

먼저 이 문제는 BFS 를 수행하는데 연결이 끝나려면 최종적으로는 사이클이 만들어져야 한다는 것입니다.

 

1 => 3 => 3

2 => 1 => 3 => 3

3 => 3

4 => 7 => 6 => 4

5 => 3 => 3

 

또한, 이미 1부터 시작하여 3을 확인하고 3이 사이클을 이룬다는 것을 확인한 뒤에는 2를 확인한 경우도 1까지 확인한 경우와 뒷부분 사이클이 같다는 것을 알 수 있습니다. 따라서 일단 한번 사이클을 확인한 부분은 더 이상 확인하지 않도록 처리하는 배열을 추가로 구성하였습니다.

 

따라서,

1. 주어진 전체 학생 수를 확인하는데 이미 학생을 확인한 경우는 패스하고

2. 확인하지 않은 경우에는 BFS 로 연결된 학생을 확인하고 사이클을 이루는 학생 수까지 확인한 뒤, 이 학생에 대해서는 더 이상 확인하지 않도록 표시를 합니다.

3. 최종적으로 전체 학생 수에서 사이클을 이루는 학생 수를 빼면 팀을 이루지 못한 학생 수를 알 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

import sys
sys.setrecursionlimit(10**6)  # 재귀함수 제한 해제


def dfs(now):
    global count
    if visited[now]:  # 이미 해당 위치를 방문한 경우 검사 x
        return

    visited[now] = True  # 현재 위치를 방문한 것으로 처리
    next_student = student[now]  # 다음 위치 얻기

    if not visited[next_student]:  # 다음 위치를 방문한 적이 없는 경우
        dfs(next_student)  # 다음 위치 방문
    else:
        if not finish[next_student]:  # 이미 방문한 위치인데 다음 위치와 연결된 그래프에서 아직 사이클을 만나지 않은 경우
            # 다음 위치는 사이클에 포함된 위치이므로 count + 1
            count += 1
            tmp = next_student
            while tmp != now:  # 다음 위치가 현 위치랑 같은 때까지 반복하면서
                count += 1  # 사이클에 포함된 수를 확인하고 count + 1
                tmp = student[tmp]

    finish[now] = True  # 현재 위치와 연결된 위치를 모두 확인해 더 이상 확인할 필요 없음


t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    student = list(map(int, sys.stdin.readline().split()))
    student.insert(0, 0)
    visited = [False] * (n + 1)
    finish = [False] * (n + 1)
    count = 0

    for i in range(1, n + 1):
        dfs(i)

    print(n - count)

 

자바 코드는 다음과 같습니다.

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

public class BJAlgo_9466 {
    private static int[] student;

    private static boolean[] visited;  // 각 학생 인덱스를 방문했는지 확인
    private static boolean[] finished;  // 이미 사이클을 확인하고 끝난 인덱스인지 확인

    private static int count; // 사이클을 생성한 인덱스의 수

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            student = new int[n + 1];
            visited = new boolean[n + 1];
            finished = new boolean[n + 1];
            count = 0;

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

            for (int j = 1; j < n + 1; j++) {
                dfs(j);
            }

            System.out.println(n - count);  // 전체 학생 수에서 사이클을 이룬 학생(팀원이 있는 학생) 수 빼기
        }
    }

    private static void dfs(int now) {
        if (visited[now]) {  // 이미 현재 위치를 확인한 경우
            return;  // 종료
        }

        visited[now] = true;  // 현재 위치를 방문한 것으로 처리
        int next = student[now];  // 다음 위치 구하기

        if (!visited[next]) {  // 다음 위치를 방문하지 않은 경우
            dfs(next);  // 다음 위치 방문
        } else {  // 다음 위치를 이미 방문한 경우 (사이클이 생김)
            if (!finished[next]) {  // 다음 위치와 연관된 사이클을 아직 확인하지 않은 경우
                count++;  // 현 위치도 사이클을 구성하므로 + 1
                for (int i = next; i != now; i = student[i]) {
                    count++;  // 사이클을 구성하는 학생 수만큼 + 1
                }
            }
        }

        // 현재 학생과 연관된 학생을 모두 확인하고 사이클까지 확인했으므로 더 이상 현 위치 확인 필요 x
        finished[now] = true;
    }
}