[BOJ/Java] 9466 텀 프로젝트

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	29504	7184	4618	24.793%

문제

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

 학생들이(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는 어느 팀에도 속하지 않는다.

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

입력

 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

 각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

 각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제 입력 1 복사

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

예제 출력 1 복사

3
0

 

 

풀이

 전형적인 DFS 문제이다.

 모든 학생에 대해서 다 완전탐색을 진행하면 무조건 터진다. for문을 돌려서 학생마다 하나하나 검사를 하게 되었을 때 모든 학생이 다 연결되어있다고 생각하면 100,000(for문 돌릴 학생 수) * 100,000(모든 학생이 link)이며 결국 O(N^2)로 범위가 100,000인 상태에서 터진다고밖에 생각할 수 없다.

 

 따라서 학생이 팀이되는 case를 잘 생각해봐야한다. 총 2 가지가 있다.

• 자기 혼자 1인 팀
• 서로서로 link되어있는 팀

 자기 혼자 있는팀은 그냥 본인이 본인을 찍은 경우이고 서로 서로 link되었다는 것은 예를들어 2 > 4 > 5 > 2 처럼 한명도 안끊기고 원을 그리는 것처럼의 형태를 띄어야 하나의 팀을 이룰 수 있다. 하나라도 이탈자가 나오면 불가능하다.

 

자기 자신만 팀인 경우와 여러명이 팀인 경우

 

 그럼 어떻게 loop를 돌려야 하느냐?

 boolean 배열을 두개 만들어서 하나는 dfs에서 방문했는지를 검토, 하나는 cycle이 돌아가는 와중에 또 방문되었는가를 확인하는지를 검토한다.

 이게 무슨말이냐. 예를 들어 우리가 2 > 6 > 4 > 1의 cycle을 돈다고 치자

start : 2
2 > 6		//visited[2] = true;
6 > 4		//visited[6] = true;
4 > 1		//visited[4] = true;
1 > 2		//if(visited[2] == true) finished[2] = true; count++;
2 > 6		//if(visited[6] == true) finished[6] = true; count++;
...

 2부터 시작한 예제의 cycle에서는 2부터 시작해서 1까지 갈때는 기본 visited 배열에 방문을 했었는지 하지 않았는지를 확인하기 위한 용도로 사용한다.

 근데 한바퀴돌아서 2를 다시봤다는 소리는 이 cycle이 한 팀을 이루기위한 조건을 충족했다는 이야기와 마찬가지이다(서로서로 다 연결되어있으므로). 따라서 지금 현재 시작한 dfs(2)의 cycle에서 loop가 도는 와중에 만난 node가 이미 visited를 충족한다면 이 node는 지금 팀에 있다는 것과 마찬가지이다.

 

 한 팀인 경우와 어떤 제한 사항으로 팀이 이루어지지 않은 예도 보면 더 쉽게 이해할 수 있다.

start : 3
3(1번째) > 3(2번째)		//visited[3] = true;
3(2번째) > 3(1번째)		//if(visited[3] == true) finished[3] = true; count++;

 

start : 1
1 > 2		//visited[1] = true;
2 > 3		//visited[2] = true;
3 > 4		//visited[3] = true;
4 > 4		//visited[4] = true;
4 > 4		//if(visited[4] == true) finished[4] = true; count++;

 두 번째가 1,2,3은 팀을 이루지 못하고 4만 팀을 이룬 경우이다. 이렇게 되었을 때 결국 1, 2, 3은 finished는 loop의 마지막에 true가 되어 cycle을 경험하였다는 표식을 남겼지만 팀을 이루지는 못한 경우가 된다.

 

 처음 이야기하였던 모든 case를 다 도는 O(N^2)와는 다르게 한번 cycle을 경험한 node는 다시 탐색하지 않기 때문에 O(N)으로 시간복잡도를 넘어갈 수 있다.

 

정답 코드

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

public class boj9466 {
    public static int count;
    public static int[] link;
    public static boolean[] finished, visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

            for(int i=1; i<=n; i++){
                if(!finished[i]){
                    dfs(i);
                }
            }
            sb.append(n-count);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    public static void dfs(int now){
        if(visited[now]){	//cycle에서 두번째 방문이라면 이미 순환구조의 팀에 포함되었음
            finished[now] = true;
            count++;	//팀에 포함되었으므로 count++
        }
        else{	//첫방문
            visited[now] = true;
        }

        int next = link[now];
        if(!finished[next]){	//cycle에 두번째 방문을 한 node는 또 dfs를 돌릴 필요없음
            dfs(next);
        }

        visited[now] = false;
        finished[now] = true;	//만약 cycle에 포함되지 않았다면 cycle경험만 충족하고 count는 올라가지 않으며 dfs가 종료됨
    }
}