설명
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(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까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
예시 입력
예시 출력
2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8
JavaScript
복사
3
0
JavaScript
복사
풀이 과정
문제의 핵심은 다음과 같습니다.
1.
사이클이 형성된다면 (즉, 같은 학생으로 돌아온다면) 팀이 결성 된 것이다.
2.
이미 끝난 팀이 형성된 학생들에 접근한다면 팀에 속할 수 없다.
3.
이미 팀이 결성되지 못하는 것이 결정된 학생에 접근하는 모든 학생들 또한 팀이 결성될 수 없다.
위 입력을 예를 들자면 다음과 같습니다.
1 → 3 → 3 (1번)
2 → 1 (3번)
3 (2번)
4 → 7→ 6→ 4 (1번)
5 → 3 (2번)
6 (2번)
7 (2번)
하지만 팀의 형성 여부, 혹은 팀이 결성되지 못하는 것을 어떻게 판별할까요?
이를 해결하기 위해 두 배열을 사용해야 합니다. visited 배열과 finished 배열입니다.
visited 배열은 방문 여부를 확인하고 finished 배열은 검증이 끝났는지 확인합니다.
다시 말해 지목 당한 학생이 이미 검증이 완료된 상태라면 그 학생이 팀을 결성 여부와 상관없이 지목한 학생은 팀을 결성하지 못하는 것입니다.
코드를 통해 한번 설명해보겠습니다.
dfs() 메소드 중 일부를 가져왔는데요, 코드를 보시면 여러 분기문이 있는 것을 확인할 수 있습니다.
현재 노드는 방문 처리하고 다음 노드를 기준으로 방문 했는지 안 했는지 판단하는데 그 이유는 다음과 같습니다.
사이클이 형성되었다는 건 다음 노드가 이미 방문한 상태여야 한다.
예를 들어, 4 → 7 → 6 → 4 일 때 4는 방문한 상태이다. 이를 사이클이 형성되었다고 판단한다.
사이클이 형성 되었다면 사이클의 수 만큼 count++ 해준다.
public static void dfs(int current) {
visited[current] = true;
int next = team[current];
if (visited[next]) {
if (!finished[next]) {
for (int i = next; i != current; i = team[i]) {
count++;
}
count++;
}
} else {
dfs(next);
}
finished[current] = true;
}
Java
복사
그렇다면 이렇게 질문할 수 있는데요, “모든 노드가 방문 처리 되는데 그 때 마다 count를 증가하는가?”
답은 아닙니다. 분기문을 보면 finished가 아닌 노드에 한해서만 count를 증가하는데요, 이는 노드를 재 방문했는데 해당 노드가 팀의 결성 여부를 판단하지 않은 노드라면 count를 추가하겠다는 것입니다.
예를 들어, 1 → 3 → 3 에서 3 → 3 은 사이클이 형성되었고 1은 되돌아 오지 못했기 때문에 count의 증가 없이 완료 처리가 됩니다.
그 후에 2 → 1을 접근했을 때 1은 이미 팀 결성 여부가 확인 되었기 때문에 1를 통한 팀 결성은 불가능하여 2 또한 완료 처리 됩니다.
이러한 일련의 과정을 거치면 팀에 속하지 않은 학생 수가 몇 명인지 쉽게 구할 수 있습니다.
최종 코드
package baekjoon.graph;
import java.io.*;
import java.util.*;
public class _9466 {
static int[] team;
static boolean[] visited;
static boolean[] finished;
static int count;
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());
for (int t = 0; t < T; t++) {
int N = Integer.parseInt(br.readLine());
team = new int[N + 1];
visited = new boolean[N + 1];
finished = new boolean[N + 1];
count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
team[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs(i);
}
}
System.out.println(N - count);
}
}
public static void dfs(int current) {
visited[current] = true;
int next = team[current];
if (visited[next]) {
if (!finished[next]) {
for (int i = next; i != current; i = team[i]) {
count++;
}
count++; // for the current node
}
} else {
dfs(next);
}
finished[current] = true;
}
}
JavaScript
복사
