[백준] 9466번 : 텀 프로젝트 (Java)

🔗 9466번 : 텀 프로젝트
● Java 풀이
● 시간 제한 3초
● 메모리 제한 256 MB

문제

 

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

 

테스트 케이스

/** 출처 (https://www.acmicpc.net/board/view/132105) **/
// input
1
11
2 10 4 5 6 7 8 9 2 2 11

// answer
8

/** 출처 (https://www.acmicpc.net/board/view/129334) **/
// input
4
3
2 3 3
4
2 3 4 2
5
2 3 4 5 4
5
1 1 1 1 1

// answer
2
1
3
4

/** 출처 (https://www.acmicpc.net/board/view/47849) **/
// input
7
6
2 3 4 5 6 2
5
2 5 4 5 2
6
1 3 4 3 2 6
13
2 4 5 2 4 1 8 9 10 11 9 10 10
10
2 5 7 1 6 8 8 3 5 10
10
2 7 10 5 3 3 9 10 6 3
6
2 1 1 2 6 3

// answer
1
3
2
8
6
8
4

 

풀이

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    private static int N;
    private static final int MAX = 100000;  // 학생 수 (1부터 시작)
    private static int[] chooses, visited;
    private static Stack<Integer> stack;

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

        stack = new Stack<>();  // 사이클 확인할 Stack
        int IS_NOT_CYCLE;  // 사이클에 속하지 않는 노드를 셀 변수
        chooses = new int[MAX + 1];  // 선택 학생 담을 배열
        visited = new int[MAX + 1];  // 방문 처리 배열

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

        for (int tc = 0; tc < T; tc++) {
            IS_NOT_CYCLE = 0;  // 사이클에 속하지 않는 노드 0으로 초기화
            N = Integer.parseInt(br.readLine());  // 학생 수 (노드 수)
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                chooses[i] = Integer.parseInt(st.nextToken());  // 선택 학생 초기화
                visited[i] = (i == chooses[i]) ? i : 0;  // 방문 배열 초기화 (자기 자신을 가리키는 학생의 경우 자기순환으로 방문 처리)
            }

            for (int i = 1; i <= N; i++) {
                if (visited[i] == 0) {  // 방문하지 않은 노드일 때
                    if (visited[chooses[i]] != 0) {  // 가리키는 노드가 이미 방문한 노드일 때
                        visited[i] = -1;  // 사이클에 속하지 않는 변수임이 확실하므로 -1로 방문 처리 (-1 = 순환하지 않는 노드)
                    } else {  // 가리키는 노드도 방문하지 않았을 때
                        //System.out.println("==== " + i + "번 노드 시작 ====");
                        findCycle(i);  // 노드 방문 함수 호출
                    }
                }
                //System.out.println("방문 여부 : " + Arrays.toString(Arrays.copyOf(visited, N + 1)) + "\n");
                if (visited[i] == -1) IS_NOT_CYCLE++;  // 순환하지 않는 노드일 경우 + 1
            }
            sb.append(IS_NOT_CYCLE).append("\n");
        }
        bw.append(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private static void findCycle(int start) {  // Stack으로 순환 노드 찾는 함수
        while (0 == visited[start]) {  // 재방문하는 노드가 나올 때까지
            visited[start] = -2;  // 방문 처리 (-2는 현재 함수에서의 임의 방문)
            stack.add(start);  // Stack에 방문 노드 삽입
            start = chooses[start];  // 가리키는 노드로 들어가기
        }

        /*
        System.out.println("이전 Stack : " + stack);
        System.out.println("방문 여부 : " + Arrays.toString(Arrays.copyOf(visited, N + 1)));
        System.out.println("start 값 : " + start);
        System.out.println("visited[start] 값 : " + visited[start]);
         */

        if (visited[start] == -2) {  // 해당 노드에서 재방문 했을 때 (= 사이클 그래프)
            while (!stack.isEmpty() && start != stack.peek()) {  // 재방문 사이클의 첫 노드가 나올 때까지
                visited[stack.pop()] = 1;  // Stack에서 순환하는 노드 방문 처리 (1 = 순환하는 노드)
            }

            if (!stack.isEmpty()) {
                visited[stack.pop()] = 1;  // 재방문 사이클의 첫 노드 방문 처리
            }
        }
        //System.out.println("이후 Stack 변화 : " + stack);

        while (!stack.isEmpty()) {
            visited[stack.pop()] = -1;  // 사이클에 속하지 않는 노드 모두 -1 방문 처리
        }
    }
}

 

만만하게 봤다가 큰 코 다친 문제.

사이클에 포함되지 않은 노드들을 세는 문제이다.

100,000명의 학생 + 테스트케이스로 인해 3초라는 시간이 엄청나게 짧게 느껴졌다.

반례도 여러 개 찾아보느라 작성한 테스트 케이스가 많은 날....ㅎㅎ

 

DFS로 푼 사람도 있다고 하는데 나는 스택으로 풀었다.

사이클을 찾을 때의 방문 처리와, 반복 작업을 하지 않기 위한 방문 처리를 한 배열에 쓰는 것이 꽤 어려웠다.

계속 방문 배열을 찍어보며 풀었던 너무너무 힘들었던 문제...