[Algorithm] Baekjoon 9466번 : 텀 프로젝트

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

9466번: 텀 프로젝트

int arr[100001];
bool visited[100001];
vector<int> tempList;
vector<int> projectMembers;
 
int DFS(int n)
{
    if (visited[n]) return n;
    visited[n] = true; // 방문체크
    int child = DFS(arr[n]); // 계속 내려가기
    tempList.push_back(child);
    if (n == child)
    {
        for (int i = 0; i < tempList.size(); ++i)
        {
            projectMembers.push_back(tempList[i]);
        }
    }
    
    return child;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t, n;
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));
        projectMembers.clear();
 
        cin >> n;
 
        for (int j = 1; j <= n; ++j)
        {
            cin >> arr[j];
        }
 
        for (int k = 1; k <= n; ++k)
        {
            if (visited[k]) continue;
            
            tempList.clear();
            DFS(k);
        }
        
        cout << n-projectMembers.size() << endl;
    }
}
 

 

재귀형식의 문제에 익숙하지 않다면 쉽게 풀지 못할 문제. 물론 나도 그랬다.

일단 재귀형식이고 사이클을 찾아야하는 것(방문했던곳을 다시 방문) 까진 얼추 접근했지만 그 이후 완벽한 로직은 생각 못해서 다른 사람 풀이방법을 찾아봤다.

return 형식 없는 풀이가 많긴 했는데, 위 코드처럼의 방식이 뭔가 제일 이해가 잘됐다.

 

방문체크 후, 이미 방문했던 곳을 찾을 때까지 재귀를 수행한다.

그러다가 방문했던 곳을 재방문, 즉 사이클이 형성된것을 탐지하면 되돌아와서 임시리스트에 child를 넣어놓는다.

그다음 리턴된 값이 현재 값과 같으면, 사이클의 출발지점을 알게 됐다는 것이다. 해당 값을 만날 때까지의 값들은 임시리스트에 전부 보관하고 있었기 때문에 해당값들을 따로 빼놓으면 된다.(projectMembers)

 

리턴된 값이 현재 값과 같지 않으면, 그대로 return child, 즉 위로 올려보낸다. 출발지점을 찾을때까지 위로 올려보낸다는 의미이다.

 

알고리즘문제가 으레 그렇듯이, 글로만 설명하기가 쉽지는 않다.

적당히 글로 이해한 다음, 테스트케이스 인풋 넣어놓고 코드흐름 보면 머리속에서 맞아 떨어지기 시작할것이다.