[Java] 백준 9466 텀 프로젝트

 

문제

학생의 수 N과 1부터 N까지의 학생이 팀을 이루고 싶은 학생 번호가 주어진다.

어떤 팀에도 속하지 않는 학생의 수를 계산해라.

- 학생 수 (2 <= N <= 100,000)

 

 

1. Deque을 이용한 풀이

- 각 학생이 선택한 학생번호를 담을 int배열 students와 확인 여부를 담을 boolean배열 visited를 둔다.

- for문을 돌며 각 학생들이 팀을 이룰 수 있는지 확인한다.

   - 아직 방문하지 않은 학생이라면 Deque에 추가

   - 현재 학생(curr)이 가리키는 다음 학생(next)을 검사

      - 방문하지 않았다면 Deque에 추가

      - 이미 방문했다면 현재 Deque에 있는 학생들로 팀을 이룰 수 있는지 검사

          - Deque의 첫번째 학생(queue.peekFirst())과 다음 학생번호(next)가 일치하는지 검사

          - 일치하지 않는다면 첫번째 학생을 Deque에서 제거하여 Deque가 빌 때까지 검사

 

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

public class b9466 {

    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());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] students = new int[N];
            boolean[] visited = new boolean[N];
            int total = N;

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

            for (int i = 0; i < N; i++) {
                if (visited[i]) continue;

                int cnt = 0;
                Deque<Integer> queue = new LinkedList<>();
                queue.add(i);
                visited[i] = true;

                loop:
                while (!queue.isEmpty()) {
                    int curr = queue.peekLast();
                    int next = students[curr];
                    if (!visited[next]) {
                        // 방문 안했으면
                        queue.add(next);
                        visited[next] = true;
                    }
                    else{
                        // 방문했으면
                        while(!queue.isEmpty()){
                            // front와 비교
                            if (queue.peekFirst() == next) {
                                cnt = queue.size();
                                break loop;
                            }
                            queue.poll();
                        }// while
                    }
                }// while

                if (cnt > 0)
                    total -= cnt;
            }// for

            sb.append(total).append("\n");
        }

        System.out.println(sb);
    }
}

 

 

2. DFS 풀이

- 각 학생이 선택한 학생번호를 담을 int배열 students, 방문 확인여부를 담을 boolean배열 visited, 덧셈 확인여부를 담을 boolean배열 checked를 둔다.

- for문을 돌며 각 학생들이 팀을 이룰 수 있는지 확인한다.

   - dfs(학생번호)를 재귀적으로 호출한다.

   - 현재 학생이 아직 방문하지 않은 상태라면 visited[학생번호]를 true로 변경하고 다음학생(next)의 방문여부를 검사한다.

   - 다음학생(next)을 아직 방문하지 않은 상태라면 dfs(next)를 호출한다.

   - 다음학생(next)을 이미 방문한 상태라면 팀을 이룰 수 있는지를 검사한다.

   - 검사한 후에 현재 학생의 checked 여부를 true로 변경한다.(호출한 쪽으로 뒤돌아가면, if(!checked[next])를 이용하여 이전 함수에서 체크했는지를 확인)

 

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

public class b9466 {
    static int total, N;
    static int[] students;
    static boolean[] visited, checked;

    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());

        while (T-- > 0) {
            total = 0;
            N = Integer.parseInt(br.readLine());
            students = new int[N];
            visited = new boolean[N];
            checked = new boolean[N];

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

            for (int i = 0; i < N; i++) {
                dfs(i);
            }

            sb.append(N - total).append("\n");
        }

        System.out.println(sb);
    }

    static void dfs(int start) {
        if (visited[start]) return;

        visited[start] = true;
        int next = students[start];

        if (!visited[next]) {
            dfs(next);
        }
        if (!checked[next]) {
            for (int s = next; s != start; s = students[s]) {
                total++;
            }
            total++;
        }

        checked[start] = true;
    }
}

 

 

채점 결과

위(DFS) 아래(Deque)