[BOJ] 9466. 텀 프로젝트(DFS, 사이클 찾기)

#. Problem

https://www.acmicpc.net/problem/9466

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

팀에 속한 학생들(사이클이 생성된 정수)의 수를 총 학생 수(N)에서 빼주면 되는

생각보다(?) 간단한 문제다.

근데 생각보다 헷갈리다...ㅋㅋㅋ

먼저 1번 학생부터 확인해보자.

1번 학생을 확인(방문)할 것이므로 visit에 체크해준다.

1번 학생은 3번 학생과 함께 팀을 이루길 원한다.

그렇다면 3번 학생을 확인해보아야 하는데,

3번 학생은 방문한적이 없으므로 방문을 해보자.

3번 학생은 3번 학생, 자기 자신과 하길 원한다.

하지만, 3번 학생은 이미 방문하였으므로 방문하지 않는다.

이미 방문한 학생을 지목했다는 것은 사이클이 생성되었다는 것이고

지목한 학생이 팀이 생성되지 않은 상태라면 팀을 만들 수 있다.

3번 학생이 팀이 생성되지 않은 상태이므로

팀을 만들어주고 팀원이 몇명인지 확인해준다.

3번의 팀원은 3번 뿐이다.

cnt++ (1)

DFS()가 종료되면서

1번, 3번 학생의 마음을 확인하였으니 

ck[]에 체크를 해준다.

다음으로 2번 학생을 확인해보자.

2번 학생을 방문했으니 visit에 체크해주고

2번 학생은 1번 학생을 지목했다.

그런데! 아쉽게도 1번 학생은 이미 방문도 했고 팀도 만들어진 상태이다.

결국 ck[]에 체크만 해주고 2번 학생은 쓸쓸히 돌아간다..

다음은 3번 학생이다.

3번 학생은 이미 방문한 상태이므로 pass

4번 학생!

4번 학생을 방문하였으니 visit에 체크해주고,

4번 학생은 7번 학생을 지목했다.

7번 학생은 다행이 방문하지 않은 상태이므로

한 번 방문을 해보자.

7번 학생을 방문(확인)했다.

7번 학생은 6번 학생을 지목했고,

다행이 6번 학생은 방문하지 않은 상태다.

6번 학생을 방문해보자.

6번 학생은 4번 학생을 지목했다. 

어랏! 근데 4번 학생은 이미 방문한 상태이다.

근데 다행이 팀은 만들어지지 않은 상태이다.

그럼 팀을 만들 수 있다 !!

팀원은 4, 7, 6번 학생이다.

DFS()가 종료되면서 4, 6, 7번 학생의 ck[]에 체크를 해준다.

다음 5번 학생은 3번 학생을 지목했는데,

3번 학생은 아쉽게도 방문한 상태이므로 paa

...

결국

{3}, {4,6,7} 로

4명이 팀이 꾸려진 상태이다.

총 7명에서 4명을 빼면 3명이 팀에 속하지 못한 학생의 수가 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <cstdio> #include <string.h> const int MAXN = 100001; int n, res, s[MAXN]; bool visited[MAXN], ck[MAXN];   void dfs(int now) {     visited[now] = true;     int next = s[now];       if (!visited[next]) dfs(next);     else if (!ck[next]) {         for (int i = next; i != now; i = s[i])             res++;         res++;     }       ck[now] = true; }   void process() {     int i;     scanf("%d", &n);     memset(visited, 0, sizeof(visited));     memset(ck, 0, sizeof(ck));       for (i = 1; i <= n; i++)         scanf("%d", &s[i]);       res = 0;     for (i = 1; i <= n; i++) {         if (!visited[i])             dfs(i);     }       printf("%d\n", n - res); }   int main(void) {     int tc;     // freopen("input.txt", "rt", stdin);     scanf("%d", &tc);       while (tc--)         process();       return 0; } Colored by Color Scripter

cs

line 33~36) n번째 학생까지 확인하지 않은 상태의 학생들을 확인

line 7~20) DFS, 

line 9) 해당 학생을 확인(방문)할 것이므로 visited에 check

line 10) 지목한 학생 정보를 저장

line 12) 지목한 학생이 아직 확인하지 않은 상태라면 확인을 하기 위해 다음 학생 정보를 넣어서 dfs() 호출

line 13~17) 이미 확인(방문)한 학생인데 팀이 만들어지지 않은 학생이라면, 팀을 만들어준다.

          해당 팀원이 몇 명인지 cnt.

line 14) 사이클이 생성되었으므로 지목한 학생들을 타고 가면서 자신이 지목될 때까지 반복

line 16) 자기 자신을 cnt

line 19) 팀이 만들어 졌거나, 만들어지지 않거나 두 경우를 확인하였으므로 ck[]에 최종적으로 check!