[BOJ] 백준 9466 - 텀 프로젝트 풀이

1. 문제

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

9466번: 텀 프로젝트

 

2. 풀이

• 백준 분류에 DFS로 분류되어 있는 문제이다.
• 문제를 보면 학생들이 자기 자신을 팀원으로 고를 수 있고, "학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다" 라고 되어있다.
• 이는 노드끼리 사이클이 발생해야 팀을 구성할 수 있다는 말과 같다.
• 그리고 출력은 어느 팀에도 속하지 않는 학생 수를 구하는 것이기 때문에 위상 정렬을 떠올렸다.
  
  
  

2-1. 위상 정렬 풀이

• 입력으로 주어지는 수열이 1번 학생부터 n번 학생까지 팀을 하고 싶은 학생 번호가 주어지기 때문이 이를 인접리스트라고 생각하여 인접리스트를 구성했다.
• 주요 자료구조
  • int[] inDegree; // 진입 차수를 체크할 배열
  • List<Integer> list; : // 팀을 이루지 못한 학생의 노드가 저장된 리스트
  • List<Integer>[] inList; // 인접리스트
• 입력을 받을 때 j 번째 학생이 고른 학생이므로 j번째 학생을 부모, 고른 학생의 번호를 자식으로 하여 인접리스트를 구성하고 진입 차수를 계산한다.
• 그 후 nonTeamStudentBFS()를 실행하여 사이클이 발생하지 않는 노드를 list에 저장한 후 list의 사이즈를 결과로 출력하면 정답이다.
  
  
  

2-2. DFS 풀이

• 백준 분류에 DFS로 분류되어 있어서 DFS로도 풀어보고 싶었다.
• 여기서는 팀을 이룬 학생의 수를 구하고 이를 n명의 학생에서 빼주는 로직으로 구성했다. 
• DFS로 풀 때는 방문처리를 할 visited 배열과 팀을 이뤘는지 체크하는 cycledNodeArr 배열을 선언했다.
• 주요 자료구조
  • List<Integer>[] inList; // 인접리스트
  • boolean[] visited; // 방문 처리 배열
  • boolean[] cycledNodeArr; // 사이클이 만들어진 노드를 처리하는 배열 , true -> 해당 노드는 사이클이 만들어졌다는 것을 의미
  •  static int result = 0; // 사이클이 만들어진 노드의 개수
• 입력을 받을 때 만약 n번째 학생이 고른 학생이 내 자신일 경우, 이미 팀일 이룬 학생이기 때문에 미리 cycledNodeArr 배열에서 true 처리를 해주었다.
• 이 다음 nonTeamStudentDFS()에서 다음과 같은 처리를 해주었다.
  1. 지금 탐색하는 노드가 이미 방문한 노드라면 
     • 방문했던 노드를 다시 방문했다는 것은 전까지 방문했던 노드와 사이클을 이룬다는 것이므로 결과 값에 +1을 해준다.
  2. 내 다음 노드가 팀을 이룬 노드라면
     • 내 다음 노드가 팀을 이룬 노드라면 다시 방문해줄 필요가 없으므로 return 처리를 해준다. 
  3. 내 다음 노드가 팀을 이룬 노드가 아니라면
     • 내 다음 노드를 방문처리 해주고, 파라미터에 내 다음 노드를 넘겨준 후 nonTeamStudentDFS()를 다시 실행한다.
     • 이 때 DFS 함수를 돌고 돌아왔다는 것은 다음 노드가 팀원을 만났을 때이기 때문에 돌아왔을 때 팀원을 이뤘다는 처리를 해줘야 한다.
     • 이렇게 처리해주면 아래와 같은 그림의 예제가 나왔을 때 2를 2번째 방문 했을 때 3은 이미 팀원 처리가 되었기 때문에 3을 또 방문하지 않는다.

3. 코드

1. 위상 정렬 코드

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

public class Main {
	static int N; // 학생수
	static int[] inDegree; // 진입 차수를 체크할 배열
	static List<Integer> list;
	static List<Integer>[] inList; // 인접리스트
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 테스트 케이스
		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			N = Integer.parseInt(br.readLine());
			
			// 입력 초기화
			inList = new ArrayList[N + 1];
			for (int j = 1; j <= N; j++) {
				inList[j] = new ArrayList<Integer>();
			}
			
			inDegree = new int[N + 1];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				int from = j;
				int to = Integer.parseInt(st.nextToken());
				
				inList[from].add(to);
				inDegree[to] += 1;
			}
			
			// 학생들의 관계를 탐색할 위상 정렬 BFS
			list = new ArrayList<Integer>();
			nonTeamStudentBFS();
			
			// 결과 출력
			bw.write(Integer.toString(list.size()) + "\n");
		}
		
		// 결과 출력
		bw.flush();
		bw.close();
		br.close();
	}

	// 위상정렬 BFS
	private static void nonTeamStudentBFS() {
		Queue<Integer> q = new ArrayDeque<Integer>();
		// 진입 차수가 0인 애들 q에 offer
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) q.add(i);
		}
		
		// 큐가 빌 때까지 
		while (!q.isEmpty()) {
			int poll = q.poll();
			list.add(poll);
			
			for (int i = 0; i < inList[poll].size(); i++) {
				if (inList[poll].get(i) != null && --inDegree[inList[poll].get(i)] == 0) {
					q.add(inList[poll].get(i));
				}
			}
		}
	}
}

2. DFS 코드

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

public class Main {
    static int N; // 학생수
    static List<Integer>[] inList; // 인접리스트
    static boolean[] visited; // 방문 처리 배열
    static boolean[] cycledNodeArr; // 사이클이 만들어진 노드를 처리하는 배열 , true -> 해당 노드는 사이클이 만들어졌다는 것을 의미
    static int result = 0; // 사이클이 만들어진 노드의 개수

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

        // 테스트 케이스
        int T = Integer.parseInt(br.readLine());
        for (int i = 1; i <= T; i++) {
            N = Integer.parseInt(br.readLine());

            // 입력 초기화
            inList = new ArrayList[N + 1];
            for (int j = 1; j <= N; j++) {
                inList[j] = new ArrayList<Integer>();
            }

            visited = new boolean[N + 1];
            cycledNodeArr = new boolean[N + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int to = Integer.parseInt(st.nextToken());

                inList[j].add(to);
                // 혼자 팀을 이루는 경우
                if (j == to) {
                    visited[j] = true;
                    cycledNodeArr[j] = true;
                    result++;
                }
            }

            // 학생들의 관계를 탐색할 DFS
            for (int j = 1; j <= N; j++) {
                if (!cycledNodeArr[j]) {  // 사이클이 만들어지지 않은 노드부터 탐색
                    nonTeamStudentDFS(j);
                }
            }

			// 결과 출력
            bw.write(N - result + "\n"); // 결과는 사이클이 만들어지지 않은 노드를 출력하는 것이므로 N - result를 한다
            result = 0;
        }

        // 결과 출력
        bw.flush();
        bw.close();
        br.close();
    }

    // DFS
    private static void nonTeamStudentDFS(int idx) {
        // 지금 탐색하는 노드가 이미 방문한 노드라면
        if (visited[idx]) {
            cycledNodeArr[idx] = true;
            result++;
        }

        // 내 다음 노드가 팀을 이룬 노드라면
        if (cycledNodeArr[inList[idx].get(0)]) {
            return;
        }

        visited[idx] = true;
        nonTeamStudentDFS(inList[idx].get(0));
        cycledNodeArr[idx] = true;
    }
}

4. 배운점

• DFS 문제를 다시 풀어봐야겠다. 하나를 배우면 하나를 잊어먹는 듯....
  
  
  

5. 점수

• 75 / 100