[Gold III] 텀 프로젝트 - 9466
성능 요약
메모리: 303204 KB, 시간: 1344 ms
분류
깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)
문제 설명
이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.
학생들이(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까지 번호가 부여된다.)
출력
각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.
풀이
많은 시간 초과를 겪었다...
방문 처리를 할 때 visit배열을 계속해서 만들어주는 게 문제였다.
dfs를 한 번 할때마다 해당 dfs에서 방문된 곳을 다시 방문하는 것이 cycle이기 때문에 visit 배열을 새로 선언하였는데, 배열을 계속 생성하는 데서 시간이 많이 소요된 것 같다.
그래서 visit 배열을 int로 선언하고 dfs를 시작할 때의 index를 start라는 매개변수로 선언하여 visit 배열의 값을 start로 정하였다.
그리고 테스트케이스에서 1 - 3 - 3 의 경우, 3은 cycle에 포함되지만 1은 포함되지 않는다.
그래서 dfs를 돌 때 order 배열에 dfs에서 방문된 순서를 각각 기록하였다.
if (visited[next]==start&& order[next] != 0) { // 이번 사이클에서 방문
cnt += (o - order[next] + 1);
return;
}
위의 코드처럼 이번 dfs에서 방문했고, 이번 index가 가리키는 값 (next=arr[i])
이 0이 아니라면, cycle이 존재한다고 판단하였다.
7
3 1 3 7 3 4 6
의 경우
4 - 7 - 6 - 4가 되면 각각의 순서는 1 2 3이 된다.
4를 다시 방문했을 때는 order[4]가 0이 아니기 때문에 order[6]=3에서 order[4]=1을 뺀 2(+1)이 사이클에 포함된 값들의 개수가 된다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] arr;
static int[] visited;
static int[] order;
static int cnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
visited = new int[N + 1];
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
cnt = 0;
order = new int[N+1];
for (int i = 1; i <= N; i++) {
if (visited[i]==0) {
dfs(i, i, 1);
}
}
sb.append(N-cnt).append("\n");
}
System.out.print(sb);
}
static void dfs(int start, int i, int o) {
order[i] = o;
int next = arr[i];
visited[i] = start;
if (visited[next]==start&& order[next] != 0) { // 이번 사이클에서 방문
cnt += (o - order[next] + 1);
return;
}
if (visited[next]!=0) return;
dfs(start, next, o + 1);
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 7579 - 앱 (자바 Java) (0) | 2022.10.21 |
---|---|
[백준] 17244 - 아맞다우산 (자바 Java) (0) | 2022.10.21 |
[백준] 17281 - ⚾ (자바 Java) (1) | 2022.10.13 |
[백준] 17136 - 색종이 붙이기 (자바 Java) (0) | 2022.10.13 |
[백준] 1931 - 회의실 배정 (자바 Java) (0) | 2022.10.12 |