문제 링크

성능 요약

1차 - 메모리: 311304 KB, 시간: 1500 ms
2차 - 메모리: 319264 KB, 시간: 1804 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 1월 17일 16:42:34

문제 설명

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

학생들이(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차 설계 : 30분

• 학생을 순회하며 아직 방문하지 않은 학생으로 탐색을 시작한다.
• 방문하는 숫자마다 큐에 넣고 4가지 조건에 따라 처리한다.
  1. 다음으로 방문할 숫자와 내가 같으면: 탐색 중 가장 마지막 노드만 팀처리 후 queue 초기화
  2. 다음으로 방문할 숫자와 시작 숫자가 같으면: queue 사이즈만큼 팀처리 후 queue초기화
  3. 이미 방문한 숫자이면: 이번 탐색 경로에 포함되는 숫자면 이전 숫자들을 제외한 후 팀처리를 해야 하고, 지난 탐색에서 이미 방문처리된 숫자면 경로 모두 무효가 되기 때문에 해당 숫자가 나올때까지 queue.poll() 한 후 queue의 사이즈만큼 팀처리
  4. 새로운 숫자이면: 다음 숫자를 방문한다.

코드(Java)

• 1차 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 텀 프로젝트_9466
 * Date: 2025.01.17
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int tc = 0; tc < T; tc++) {

            int n = Integer.parseInt(br.readLine());
            int[] next = new int[n+1];
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= n; i++) next[i] = Integer.parseInt(st.nextToken());

            boolean[] visited = new boolean[n+1];
            Queue<Integer> queue = new ArrayDeque<>();
            int notTeam = n;

            for (int i = 1; i <= n; i++) {
                if (visited[i]) continue;

                int curr = i;
                while (true) {
                    visited[curr] = true;
                    queue.add(curr);

                    if (next[curr] == curr) {
                        notTeam--;
                        queue.clear();
                        break;
                    } else if (next[curr] == i){
                        notTeam -= queue.size();
                        queue.clear();
                        break;
                    } else if (visited[next[curr]]) {
                        while(!queue.isEmpty() && queue.peek() != next[curr]) queue.poll();
                        notTeam -= queue.size();
                        queue.clear();
                        break;
                    }
                    curr = next[curr];
                }
            }
            bw.write(String.valueOf(notTeam)+ "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

2차 설계 : 20분

• 학생을 순회하며 아직 방문하지 않은 학생으로 탐색을 시작한다.
• 방문하는 숫자를 방문처리하며 동시에 set에 추가한다.
• 이미 방문한 숫자를 만나면 그 숫자를 반환한다.
• 마지막에 막힌 숫자(반환된 숫자)가 set에 존재하는 동안 notTeam의 수를 줄이고, 스스로를 만나면 set에서 삭제한다.
• 팀처리를 위해 다시 queue.poll()를 전체 실행했던 풀이를 개선하고자 시도해봤지만 결과적으로는 더 오래걸렸다.
• 일괄처리 부분도 존재하던 이전 코드와 달리 모든 탐색 경로에 대해 하나씩 다시 처리를 해주는 구조라서 그런지 모르겠다.

코드(Java)

• 2차 구현 시간: 40분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 텀 프로젝트_9466
 * Date: 2025.01.17
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    static int[] next;
    static boolean[] visited;
    static int notTeam;
    static Set<Integer> passed;

    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int tc = 0; tc < T; tc++) {

            int n = Integer.parseInt(br.readLine());
            next = new int[n+1];
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= n; i++) next[i] = Integer.parseInt(st.nextToken());

            visited = new boolean[n+1];
            notTeam = n;

            for (int i = 1; i <= n; i++) {
                if (visited[i]) continue;
                visited[i] = true;
                passed = new HashSet<>();
                passed.add(i);
                if(checkNext(next[i]) == i) notTeam--;
                passed.clear();
            }
            bw.write(String.valueOf(notTeam)+ "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int checkNext(int curr) {
        if (visited[curr]) return curr;

        passed.add(curr);
        visited[curr] = true;

        int last = checkNext(next[curr]);
        if (passed.contains(last)) {
            notTeam--;
            if (last == curr) passed.remove(last);
        }
        return last;
    }
}