[TIL] 24.02.15

1. 알고리즘 문제 해결

 

 

텀 프로젝트(백준 9466):

 사이클에 포함되지 않는 원소의 수를 찾는 문제이다. DFS를 사용하는 것은 명확했는데 시간초과 때문에 애를 먹었다. 스택을 사용해서 풀려고 시도하니까 자꾸 시간초과가 났다. 탐색에 있어서 방문처리를 위한 자료구조와 사이클을 위한 자료구조를 따로 사용하다보니, 그렇게 된 것 같다.

 둘 다 Vector로 이용하면 매번 초기화 과정에서 시간을 많이 사용하게 돼서, Set을 이용해보기도 했는데 조금 더 많은 테스트 케이스를 통과하긴 했지만 결국 시간초과가 났다. 탐색을 진행하다가 방문한 노드에 도달하게 되면 사이클을 찾은 것으로 판단하고, 역으로 순회하며 사이클 포함처리를 해주는 로직이었는데, 내가 아는 선에서는 더 이상 시간 복잡도를 줄이기 힘들어 보였다.

 그래서 어쩔 수 없이 재귀를 이용한 DFS를 사용해 필요한 자료구조를 하나로 줄였고, 그제서야 통과할 수 있었다. 메모리 낭비가 많은 느낌이라 재귀를 이용하는 것을 선호하지는 않는데, 오히려 그 생각 때문에 한참 돌아가게 된 것 같다.

 

#pragma GCC optimize("Ofast")

#include <iostream>

#include <vector>

using namespace std;

vector<int> nodes;

vector<int> isVisited;

int dfs(int now) {

    int next = nodes[now];

    int cycleCnt = 0;

    if(isVisited[next] == 0) {

        isVisited[next] = isVisited[now] + 1;

        cycleCnt = dfs(next);

    }else {

        cycleCnt = isVisited[now] - isVisited[next] + 1;

    }

    isVisited[now] = 100001;

    return cycleCnt<0 ? 0 : cycleCnt;

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    int t, n;

    cin >> t;

    for(int i=0; i<t; i++) {

        cin >> n;

       

        nodes = vector<int>(n+1);

        isVisited = vector<int>(n+1, 0);

        for(int j=1; j<=n; j++) {

            cin >> nodes[j];

            isVisited[j] = 0;

        }

       

        int cnt = 0;

        for(int j=1; j<=n; j++) {

            if(isVisited[j] == 0) {

                isVisited[j] = 1;

                cnt += dfs(j);

            }

        }

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

    }

}