BOJ_9466 : 텀 프로젝트

👉 문제링크

---

---

🔸 문제 분석 🔸

• T번의 테스트 케이스안에서 다음과 같은 입력이 주어진다.
• n명 (2~10만)의 학생 수가 주어지고, 다음 줄에 각 학생이 같이 팀을 하고 싶은 학생의 번호가 주어진다.
• 자기 자신을 뽑거나, 팀을 하고싶은 학생들끼리 순환구조(서클)이 만들어지면 팀을 만들 수 있다.
• 최종적으로 팀에 속하지 않은 학생의 수를 출력한다.

🔸 문제 풀이 🔸

1. 제한시간 3초에 각 테스트 케이스의 n이 10만이기 때문에 O(n^2)의 알고리즘은 사용할 수 없다.
2. 팀이 만들어지는지 확인하기 위해 깊이 우선 탐색(DFS)를 사용한다.
3. DFS의 경우의 수는 다음과 같다.
   
   1. 1) 탐색하다가 시작 번호를 다시 찾음 : 탐색한 모든 학생들은 같은 팀
   2. 2) 탐색하다가 중간 번호를 다시 찾음 : 중간 번호까지 팀이고, 시작 번호부터 중간 번호 사이는 팀을 만들 수 없음
   3. 3) 이미 팀 소속이 있는 번호 : 시작 번호부터 현재까지 모두 팀을 만들 수 없는 학생 번호
4. n명의 학생들이 모두 번호를 가리키고 있으므로, DFS 탐색은 항상 위 3가지 경우의 끝을 보게 된다. 그리고 1번과 2번은 사실상 같은 경우라고 볼 수 있다.
5. 중요한건 한번 탐색한 번호는 다시 DFS를 탐색하지 않게해서 O(n)의 시간 복잡도를 만드는 것이다.

🔸 코드 🔸

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

public class Main {

    private static int[] pick, visited;
    private static boolean[] isTeam;

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

        int T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine());
            pick = new int[n];

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

            int cnt = 0; // 팀이 없는 애들 수
            isTeam = new boolean[n]; // 팀 소속 여부
            visited = new int[n]; // 방문 체크
            Arrays.fill(visited, -1);
            for (int i = 0; i < n; i++) {
                if (visited[i] == -1 && !isTeam[i]) { // 방문 안했고, 팀 없으면 dfs 돌림
                    dfs(i, i);
                }
                if (!isTeam[i]) { // dfs 후에도 팀 없으면 카운트
                    cnt++;
                }
            }
            sb.append(cnt).append('\n');
        }
        bw.write(sb.toString());
        bw.flush();
    }

    private static int dfs(int now, int start) {
        // 방문 했었음
        if (visited[now] > -1) {
            if (visited[now] == start) { // 현재 탐색에 방문함 : 서클 발생
                isTeam[now] = true;
                return now;
            } else { // 팀이 있음 or 이전 방문
                return -1;
            }
        }

        visited[now] = start;

        // 재귀
        int result = dfs(pick[now], start);

        if (result > -1 && now != result) { // 현재 서클 안쪽임
            isTeam[now] = true;
            return result;
        }

        // 재귀 되돌아 가며 처리 할 거 없음, 서클종료
        return -1;
    }
}

🔸 코드 해석 🔸

• 학생 별 선택 번호를 저장하는 int 배열 pick, 팀 소속이 있음을 나타내는 boolean 배열 isTeam, 탐색 시 시작 번호를 저장하는 int배열 visited를 사용했다.
• n개의 번호에 다음과 같은 계산을 반복한다.
  • 방문하지 않았고, 팀이 없으면 dfs() 메서드를 돌린다.
  • 이후에도 팀이 없으면 cnt를 +1 한다.
• dfs 재귀 메서드에서는 다음과 같은 계산을 반복한다.
  • 방문 확인
    • 현재 탐색에 방문했던 번호라면, 서클이 발생한 것이므로, 다시 현재 번호가 나올 때 까지 isTeam[now]을 true로 젖아하고 now를 반환한다.
    • 이전 탐색 방문했던 번호라면, 서클이 만들어지지 않으므로 -1을 반환한다.
  • 방문하지 않았던 번호라면 방문처리한다.
  • 재귀 결과 처리
    • dfs(pick[now], start) 로 다시 재귀 메서드를 실행한다.
    • 만약 재귀 메서드의 반환값 result가 0이상이고 now와 다르다면, 서클 중간이므로 istTeam[now]를 true로 바꿔주고 result를 반환한다.
  • result가 -1이거나 result == now라면 서클이 종료된 것이므로 -1을 반환한다.

---

🔸 end 🔸

•  단순한 DFS 알고리즘만 필요한 문제인데, 난이도가 꽤 높았던 것 같다.
  • 각 테스트 케이스 실행의 시간 복잡도를 O(n)으로 해야돼서 1회 시간 초과 났다.
  • 2번째 제출의 틀렸습니다는 이전 탐색에서 팀이 없음을 알았는데, 현재 탐색에서 다시 방문해야 할 경우에 오류가 나서 틀렸다. visited를 처음엔 boolean 배열로 뒀다가, 이 문제를 해결하기 위해 start를 기록하고 visited를 int배열로 바꿔서 처리했다.
• 구현하는 방법이 다양하게 있는 문제인 것 같다.
  • 테스트 케이스를 다양하게 돌려보면서 디버깅 하는게 중요한 것 같아서, 직접 만들기도 하고 질문 게시판에 있는 반례들을 모으기도 했다.
  • 테스트 케이스 모음을 질문 게시판에 남겨놓았다.