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

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

개인적으로 이 문제는 너무나도 어려웠다. 

기본적인 접근으로는 dfs 싸이클만 탐색이 가능하다면 풀 수 있을 것이라고 생각하고 접근하였으나...

배열size가 2차 배열일 경우 100000 * 100000 이므로 size는 오바되기 떄문에 1차배열을 사용해야만 했다.

따라서, 1차 배열을 사용시에 4 -> 7 -> 6 .. -> 4 -> 7 -> 6 이라는 싸이클을 탐지해야하는 부분이 어려웠다.

이 부분을 해결하기위해서 visit배열 이외에 2가지를 추가했다.

1. finished라는 배열을 두어서 방문하는 것 이외에 사이클이 되는지 확인하는 배열을 추가했다.

2. cycle_chk배열로 finished배열이 false일 경우 cycle이 되는 정점의 갯수를 카운터해준다. 

 

#include<iostream>

using namespace std;

#include<algorithm>

#include<cstring>

int testcase, n, arr[100010],cnt,first,cycle_chk[100010];

bool visit[100010],finished[100010];

//cycle_chk 배열은 사이클 함수들어갈때 사이클 확인하게 해주는 배열

void cycle(int idx, int next)

{

cnt++;

if (idx == next)return;

cycle(cycle_chk[idx], next);    // 이 부분을 따로 cycle_chk가 아니라 arr배열을 사용하면 4 -> 7 -> 6에서 (6,4)가 입력되고, 재귀호출후 4==4로

}                                          //    2번의 카운터 이후 종료된다(정답이라면 3번이 카운터되야됨,, why? 4-> 7로 넘어가는 부분이 없음)                      

void dfs(int i)

{

visit[i] = true;

int next= arr[i];

if (!visit[next])

{

cycle_chk[next] = i;        // 사이클 함수를 수행하기 위해 해당 정점을 넣어두는 함수. 

dfs(next);

}

else {

if (!finished[next])

{

cycle(i, next);

}

}

finished[i] = true;     // 이 부분을 통해서 그 전에 사이클의 존재여부를 수행했는지를 true로 설정해준다.

}

int main()

{

cin.tie(0);

ios::sync_with_stdio(false);

cin >> testcase;

while (testcase--)

{

cin >> n;

for (int i = 1; i <= n; i++)

{

cin >> arr[i];

}

for (int i = 1; i <= n; i++)

{

if (!visit[i])

{

first = i;

dfs(i);

}

}

cout << n - cnt << "\n";

cnt = 0;

memset(arr, 0, sizeof(arr));

memset(visit, 0, sizeof(visit));

memset(finished, 0, sizeof(finished));

}

return 0;

}