[백준 자바 9466] 텀 프로젝트 (골드 3)

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

9466번: 텀 프로젝트

 

 

맨 밑에 전체 코드 있습니다. 

 

문제설명

텀 프로젝트를 위해 학생들은 서로 팀을 이뤄야 한다. 팀의 조건은 다음과 같다. . 

• 한 학생은 1명의 학생을 가리켜야 한다. 자기자신도 상관 없다. 
• 학생들이 서로 가리키다가 싸이클이 형성되면 하나의 팀이 된다. 이때 자기자신을 가리키면 혼자 한 팀이다. 

출력은 팀을 이루지 못한 학생 수이다

 

학생번호	1	2	3	4	5	6	7
학생이 가리킨 학생번호	3	1	3	7	3	4	6

 

위 표는 문제에 있는 예제이며, 첫 열을 보면 1번 학생이 3번 학생을 가리키고 있다는 뜻이며, 3열로 가면 3번 학생이 3번 학생을 가리키고 있다는 뜻이므로 (1->3->3) 3 혼자 팀이 이뤄진다.

 

정리하자면, 

2 -> 1 -> 3 -> 3

5 -> 3 -> 3

4 -> 7 -> 6 -> 4

로 항상 끝에는 싸이클이 형성된다는 것을 알 수 있다. (3-3, 4-7-6으로 2개)

 

 

아래: 시작학생, 오른쪽: 도착학생	1	2
1	inf	1
2	1	inf

이는 행을 시작학생, 열을 도착학생으로 하는 2차원 배열로 할 수도 있지만, 그렇게 구현하게 되면 O(N^2) 이며, 학생수는 최대 10만명 이므로 시간초과가 되게 된다. 따라서 방문체크 배열인 visited 외에도 finished 배열을 추가로 만들어준다. 

• boolean[] visited : 방문한 노드인지 체크하는 배열. 
• boolean[] finished : 싸이클을 계산해본 노드인지 체크하는 배열. 

 

만약 1 -> 3 -> 3 으로 싸이클을 한번 계산해봤고, 이를 finished에 저장해뒀다면, 1 노드로 진입 시 이 이후는 싸이클을 형성한다는 것을 알고 있다. 그래서 2 -> 1 -> 3 -> 3 진행 시 2에서 1로 가는 시점에서 이 이후는 싸이클이 형성된다는 것을 finished 배열로 알 수 있고, 이후 더 진행하지 않는다. 마찬가지로 5 -> 3 -> 3 역시 5에서 3으로 진입 시 더 이상 진행하지 않는다. 

 

 

이제 부분적으로 코드를 나눠서 설명하자면, 

• 먼저 stoi 함수는 String to int 로, 문자열을 숫자로 바꿔주는 함수인데 편의상으로 적어뒀다. 
• 학생수를 N에 입력 받고, 
• arr는 위의 예제의 표에서 학생번호를 0부터 시작하도록 한 배열이다. (문제에선 학생번호가 1부터 시작이다)
• 그리고 visited, finished 배열은 아까 설명했으니 넘어가고, 
• 마지막으로 count 는 팀을 이룬 학생수를 센다. 

 

• 그다음 메인함수를 실행하는데, 테스트 케이스를 위한 T를 받아 그 횟수만큼 반복을 한다. 
• 그리고 각 테스트 케이스에서는 static 변수들을 재대입 해준다. 
• 그리고 arr 배열의 값에 가리키는 학생번호를 입력하는데, 학생번호를 0부터 시작하기로 했으므로 1씩 빼준다. 
• 그리고 각 학생들을 돌아가며 백트래킹을 돌려주며, 
• 마지막으로 전체 학생수 N에서 팀을 이룬 학생수 count를 빼주어 팀을 이루지 못한 학생수를 출력한다. 

 

 

 

 

 

• 먼저 now는 현재 학생을 가리키며, 만약 방문했다면 리턴한다.
• 방문하지 않았다면 방문처리를 한 뒤, 현재 학생이 가리키는 다음 학생을 next 로 불러온다. 
• 만약 다음 학생도 방문하지 않았다면 계속 방문하며, 
• 만약 방문했지만 아직 싸이클을 이루는지 계산을 안 해본 학생이면 (= finished가 false인 학생이면), 싸이클 계산을 시작한다. 
• 이 부분은 밑에 더 자세히 설명하고 넘어가면, 
• 마지막으로 싸이클을 이루는지 계산이 끝났으면 지금까지 돌았던 노드들을 전부 finished를 true 처리하며 함수를 끝낸다. 

 

먼저 arr 배열에는 0부터 시작하는 학생번호의 값이 있고, bt(3)으로 예를 들자면, (위의 그래프 예제에서 1씩 값을 뺐다), 3의 다음 학생인 6, 6의 다음학생은 5는 방문하지 않았으므로 계속 bt를 타고가다가, now가 5이고 next가 3인 시점에서, 3은 방문을 했고 또 싸이클을 이루는지 계산되지 않았다(finished가 false). 따라서 싸이클을 다시 타고 돌아가면서 count++ 를 해주게 된다. 

 

for문에서 next는 싸이클을 시작하는 학생인 3이고, 싸이클의 끝에 있는 학생인 5에서 멈춰야 하며, 싸이클을 이루는 동안 쭉 돌아야 한다. 

마지막 now 인 5번 학생은 for문이 안 돌기 때문에 for문 밖에 count++ 를 해준 뒤 함수를 끝낸다. 

 

위는 bt(0)을 끝낸 이후의 그래프이고, 0 -> 2 -> 2 이므로 0을 진입하게 되면 이후는 싸이클로 끝난다는 것을 finished 로 알기 때문에 bt(1)나 bt(4)는 중간에 함수가 끝나게 된다. 

 

마지막으로 전체 학생수인 N에서 팀을 이룬 학생수 count 를 뺀 값을 출력하면 된다. 

 

---

 

전체 코드

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

public class Main {
    static int stoi(String s) { // String to int 함수
        return Integer.parseInt(s);
    }

    static int N; // 입력 개수
    static int[] arr; // 0번부터 N-1번의 학생을 인덱스로 하고, 그 인덱스의 값을 학생이 가리키는 다른 학생 번호로 하는 배열
    static boolean[] visited; // 방문한 학생을 체크하는 배열
    static boolean[] finished; // 방문한 학생들중 싸이클을 계산했었는지 체크하는 배열
    static int count; // 팀을 이룬 학생을 셈

    public static void main(String[] args) throws IOException {
        // 자바는 입력을 이렇게 받는다.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = stoi(br.readLine()); // 테스트 케이스를 한줄 입력 받아서 String to int 로 변환
        for (int i = 0; i < T; i++) { // 각 테스트 케이스만큼 반복문 돌려주기
            N = stoi(br.readLine()); // 한 테스트 케이스 동안 입력으로 오는 학생수 받기.
            arr = new int[N]; // 특정 학생이 가리키는 학생을 값으로 가지는 배열
            visited = new boolean[N]; // 방문 체크
            finished = new boolean[N];
            count = 0; // 0으로 초기화하여 매 테스트 케이스에 독립적.

            // 이 클래스로 자바는 공백을 기준으로 쪼갠다.
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < N; j++) { // N번만큼 학생이 가리키는 학생번호 입력받기
                arr[j] = stoi(st.nextToken()) - 1;
            }

            for (int j = 0; j < N; j++) { // 각 학생들을 돌아가며 백트래킹 돌리기
                if (!visited[j]) {
                    bt(j);
                }
            }
            // 팀을 못 이룬 학생수를 출력해야하므로, 전체 학생수 - 팀이룬 학생수
            System.out.println(N - count);
        }
    }

    static void bt(int now) { // 백트래킹
        if (visited[now]) return; // 방문 했으면 리턴

        visited[now] = true; // 방문 안 했으면 했다고 체크
        int next = arr[now]; // 그 학생이 가리키는 다른 학생 번호 가져오기

        if (!visited[next]) { // 그 학생도 방문 안 했다면
            bt(next); // 방문
        } else if (!finished[next]) { // 방문 했는데 아직 처리 안 했다면,
            count++;
            // 싸이클의 시작이자 끝부터(next) 계속 가리키는 학생을 돌며 현재 학생(now, 싸이클의 시작과 끝을 가리키는 학생)이 되면 끝.
            for (int i = next; i != now; i = arr[i]) {
                count++;
            }
            // 싸이클을 이루는 학생 수 카운팅.
        }

        finished[now] = true; // 싸이클이 완성된 후, 싸이클 계산이 끝났다는 것을 체크
    }
}

 

참고자료

https://bcp0109.tistory.com/32

백준 9466번. 텀 프로젝트 (Java)