[백준 알고리즘][DFS] 9466번 텀 프로젝트

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(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까지 번호가 부여된다.)

출력은 각 테스트케이스마다 프로젝트 팀에 속하지 못한 학생들의 수를 나타낸다.

풀이

입력받은 한명의 학생이 하나의 vertex이고 사이클이 있을 경우 해당 사이클에 속하는 아이들을 빼고 나머지가 프로젝트 팀에 속하지 못한 학생들의 수이다 DFS로 사이클을 찾는다

인접리스트를 만들면(그냥 1차원 배열에 넣음)

1->3

2->1

3->3

4->7

5->3

6->4

7->6

다음과 같이 된다 for문을 통해서 1부터 7까지 전부 돌면서 DFS할거다 방문했는지를 확인하는 VISITED배열을 만든다

처음 i = 1에서 시작하면 시작점을 담아놓을 변수 start = i로 만들어주고 visited[1]=VISIT이 된다 그리고 다음 방문할 곳은 student[1]가 된다 그러면 i=student[i]가 되고 i=3이 된다 그리고 visited[i]=VISIT이 되고 그다음 방문할 곳은 i=student[3] 이므로 3이다 3은 이미 방문한곳이기때문에 방문했을때 이 변수랑 start가 같은지 보고 같으면 싸이클이 된다는 것을 알 수 있다 이렇게 끝까지 방문을 했을때 그 끝vertex와 start가 같지않으면 i++하고 다음 시작점에서 시작을 하고 이때 다시 visited는 초기화해야한다 만약 싸이클이 있다면 그 싸이클을 다시 돌아볼 필요없으므로 visited에서 초기화하지않는다

일단 짜긴 다 짰는데 비효율적이라 생각했는데 바로 시간초과 떴다... 3번이나 시간초과 ㅠㅠ

최대한 필요없는 DFS 탐색은 줄였는데 for문이 많아서 그런지...............

시간은 줄여서(초기화부분을 없애서) 시간초과를 없앴는데 예외케이스가 많다

1

3

2 3 2

가 입력될 경우에 1->2->3->2 로 갈때 이 부분안에서 2->3->2 부분의 사이클을 찾아내야한다

나는 1->2->3->2로가면 1,2,3 모두 visit이 되어서 다 사이클을 포함하고 있지않다고 판단해서 3명이 프로젝트에 참여하지 않는 학생수가 되버린다...

바보다 DFS쓸려고 해놓고 스택도 안만들고.......

스택만들어서 1->2->3->2 와 같은 사이클도 찾기 위해서 방문할때마다 스택에......

아 너무 오랜만에 풀다보니까 하루종일 헷갈렸다 DFS쓸려면 스택이 필요한게 맞다! 

DFS로 잘 풀어놓고 원래 이상한말 써놨었네.. 부끄러우니까 수정해야지 앞으로 진짜 손으로 좀 정리해가면서 풀어야겠다