[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;
}
}
채점 결과
