백준 알고리즘: 9466번 텀 프로젝트

문제 정보

---

 

9466번: 텀 프로젝트

 

 

핵심

---

DFS(깊이 우선 탐색)으로 순환을 이루는 학생들을 찾아야 한다

visited 배열을 사용하여 방문한 학생들을 재방문하지 않도록 처리해 주어야 하며

재귀적으로 노드들을 탐색할 때, 해당 부분집합에 순환되는 부분이 존재할 수 있으므로

이를 골라내어 카운팅해주는 방식이 요구되는 것 같다

 

처음에는, 재귀 호출로 구한 여러명의 학생들 중 일부만 순환 관계에 놓여있다고 했을 때

순환을 이루는 학생들에 대해서만 방문 표시를 해주고, 나머지 학생들에 대해서는 방문 표시를 다시 안함(false)로 되돌려 주었는데

어차피 나머지 학생들은 그 어떤 누구와도 순환 관계를 이룰 수 없으므로 이들 또한 방문 표시를 해 주어

비효율적인 반복이 이루어지지 않도록 설정해 주는 것이 핵심이라고 생각했다

 

public static int dfs(int currentPos, int startPos) {
    selected[currentPos] = true;
    set.add(currentPos);
    int nextPos = select[currentPos] - 1;

    if (!selected[nextPos]) {
      return dfs(nextPos, startPos);
    } else {
      if (set.contains(nextPos)) {
        int count = 1;
        int start = nextPos;
        int current = select[start] - 1;
        while (start != current) {
          current = select[current] - 1;
          count++;
        }
        return count;
      }
    }
    return 0;
  }

이 방법에 대한 구현으로는, Set자료형을 선언하고 재귀적으로 호출된(이어진) 학생들을 Set에 넣고

만약 다음에 방문해아 할(선택의 결과에 해당하는) 노드가 방문했던 노드이면서

Set(현재까지 방문했던 노드들의 집합)에 존재한다면 순환 관계가 있다고 보고

 

    if (!selected[nextPos]) {
      return dfs(nextPos, startPos);
    } else {
      if (set.contains(nextPos)) {
        int count = 1;
        int start = nextPos;
        int current = select[start] - 1;
        while (start != current) {
          current = select[current] - 1;
          count++;
        }
        return count;
      }
    }

마지막에 방문하려 했으며, 이미 방문했던 노드(nextPos)를 시작으로 순환 관계에 있는 노드들을 파악하여 카운팅 해 주고

이를 return하면 한 순환 관계에 놓인 학생들의 수를 찾을 수 있게 된다

 

      for (int s = 0; s < n; s++) {
        if (!selected[s]) {
          set.clear();
          result -= dfs(s, s);
        }
      }

이는 모든 학생에 대하여 수행하되, 이미 방문했던 학생에 대해서는 수행하지 않는다

result에는 전체 학생의 수를 대입해 놓고, 순환 관계에 놓인 학생의 수(dfs(s, s))를 빼 나가면서

문제에서 요구하는 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산해 나갈 수 있다

 

 

풀이

---

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

public class Main {

  static int[] select;
  static boolean[] selected;
  static Set<Integer> set;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int test_cases = Integer.parseInt(br.readLine());
    for (int i = 0; i < test_cases; i++) {
      int n = Integer.parseInt(br.readLine());
      select = new int[n];
      String oneLine = br.readLine();
      StringTokenizer st = new StringTokenizer(oneLine);
      for (int s = 0; s < n; s++) {
        select[s] = Integer.parseInt(st.nextToken());
      }
      selected = new boolean[n];
      set = new HashSet<>();
      int result = n;
      for (int s = 0; s < n; s++) {
        if (!selected[s]) {
          set.clear();
          result -= dfs(s, s);
        }
      }
      System.out.println(result);
    }
  }

  public static int dfs(int currentPos, int startPos) {
    selected[currentPos] = true;
    set.add(currentPos);
    int nextPos = select[currentPos] - 1;

    if (!selected[nextPos]) {
      return dfs(nextPos, startPos);
    } else {
      if (set.contains(nextPos)) {
        int count = 1;
        int start = nextPos;
        int current = select[start] - 1;
        while (start != current) {
          current = select[current] - 1;
          count++;
        }
        return count;
      }
    }
    return 0;
  }
}

 

 

Source Code on GitHub

---