[백준] 9466번 : 텀 프로젝트

문제

 

 

접근 방식

정말 x 9999 어렵게 풀었다...

시간초과가 테스트케이스의 1%, 32% 83%에서 발생해서 해결하느라 애먹었다

 

문제 분류를 살펴보면 DFS지만 BFS가 아직은 더 편해서 BFS를 사용해서 풀었는데

우선 문제를 이해부터 하고 시작하겠다.

 

사이클을 찾아서 사이클이 존재하지 않는 경우가 몇 개인지 찾는 문제로

1	2	3	4	5	6	7
3	1	3	7	3	4	6

 

위 예제의 경우에는 3번은 자기 자신으로 바로 돌아와서 혼자 팀을 하는 사이클이 존재하고

4, 6, 7번은 4 > 7 > 6 > 4라는 사이클이 존재한다.

 

이외의 경우는 자기 자신으로 돌아오는 사이클이 존재하지 않는데

여기서 자기 자신으로 돌아오는 사이클이 없는 경우가 바로 팀에 속하지 않는 경우다.

 

 

발그림으로라도 설명을 해보자면 완전한 사이클을 이루는 경우를 제외한

다른 모든 경우가 사이클을 만나면 해당 경우를 사이클이 존재하지 않는다고 판단할 수 있는데

3은 혼자 자기 자신으로 돌아오는 하나의 완전한 사이클을 가지고 있고

1은 이러한 사이클에 끼어들 수 없으니 사이클을 만들 수 없게 되고

2도 당연히 사이클을 만들 수 없는 1을 마주치니 사이클을 만들 수 없다.

 

즉, 1 > 3 > 2 > 1이 되면 사이클이 될 수 있지만, 3에서 사이클이 존재하기 때문에

1과 2는 사이클을 만들 수 없게 되는 것이다.

 

정리하자면 이미 존재하는 사이클을 만나거나 사이클을 만들 수 없는 학생을 마주치면

해당 학생은 사이클이 될 수 없어서 팀을 꾸릴 수 없는 학생이고

자기 자신으로 돌아오는 경우에는 중간에 거친 모든 학생과 팀을 이룰 수 있다.

 

코드로 구현해야 하는 것은 크게 두 가지인데

 

사이클을 만나거나 사이클이 될 수 없는 학생과 마주친 경우

이전에 지나친 모든 학생들을 사이클이 될 수 없는 학생으로 기록하는 것 = 팀을 이룰 수 없는 학생

 

자기 자신으로 돌아오는 사이클이 존재하여

이전에 지나친 모든 학생들을 사이클이 될 수 있는 학생으로 기록하는 것 = 팀을 이룰 수 있는 학생

 

위 두개의 로직을 코드로 구현해주면 된다.

 

테스트 케이스가 빡새 시간이 생각보다 타이트한 문제로 탐색의 종료 시점과

건너뛸 부분을 잘 처리해줘야 한다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(br.readLine());
			int count = n;
			st = new StringTokenizer(br.readLine());

			int[]students = new int[n];
			int[] arr = new int[n];

			boolean[] isCycle = new boolean[n];
			boolean[] isNotCycle = new boolean[n];

			for (int j = 0; j < n; j++) {
				int select = Integer.parseInt(st.nextToken()) - 1;

				students[j] = select;

				if (j == select) {
					isCycle[j] = true;
					count--;
				}
			}

			for (int j = 0; j < n; j++) {
				if (isCycle[j] || isNotCycle[j]) continue;

				int select = students[j];

				arr[0] = j;

				int size = 1;

				while (true) {

					if (isCycle[select] || isNotCycle[select]) {
						for (int k = 0; k < size; k++) {
							isNotCycle[arr[k]] = true;
						}
						break;
					}

					if (j == select) {
						for (int k = 0; k < size; k++) {
							isCycle[arr[k]] = true;
						}
						count -= size;
						break;
					}

					if (size >= count) {
						isNotCycle[j] = true;
						break;
					}

					arr[size++] = select;
					select = students[select];
				}
			}

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

		System.out.println(sb);
	}
}