백준 9466번 텀 프로젝트

🔒[문제 url]

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

🔑알고리즘

DFS를 통해 $cycle$을 찾는 문제이다.
이때, 한 학생을 탐색하기 위해서 판단할 조건은 다음 두 가지이다.
1. 아직 방문하지 않은 학생인가?
2. 이미 방문했으나, $cycle$을 이루지 않는 학생인가?

이때, 방문 여부와 $cycle$ 여부를 판단하기 위해 두 개의 배열을 선언한다.

• 2번의 경우, 현재 학생과 다음 학생이 하나의 $cycle$에 있음을 의미한다.
  $N$에서 모든 $cycle$의 길이의 합을 뺀 것이 답이 된다.

🐾부분 코드

int t,n;
int li[100001];
bool visited[100001];
bool cycle[100001];

<변수 선언>
2번 조건을 판별하기 위해 visited와 cycle 배열을 선언한다.

int DFS(int now)
{
    int ret = 0;

    visited[now] = true;

    if(!visited[li[now]]) ret = DFS(li[now]);
    else if(visited[li[now]] && !cycle[li[now]])
    {
        ret++;
        for(int i = li[now]; i != now; i = li[i])
            ret++;
    }

    cycle[now] = true;
    return ret;
}

<DFS 함수>
$cycle$을 발견할 때마다 $cycle$에 속하는 학생 수를 구하여 반환한다.

void SOLVE()
{
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> li[i],
            visited[i] = false,
            cycle[i] = false;

        int cnt = 0;
        for(int i = 1; i <= n; i++)
            if(!visited[i]) cnt += DFS(i);
        cout << n - cnt << '\n';
    }
}

<Testcase 반복>
초기화에 유의하여 testcase만큼 반복한다.
$N$-(DFS 함수에게 반환받은 값)이 출력 답안이 된다.

🪄전체 코드

#include <iostream>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int t,n;
int li[100001];
bool visited[100001];
bool ban[100001];

void INPUT()
{
    IAMFAST
    cin >> t;
}

int DFS(int now)
{
    int ret = 0;

    visited[now] = true;

    if(!visited[li[now]]) ret = DFS(li[now]);
    else if(visited[li[now]] && !ban[li[now]])
    {
        ret++;
        for(int i = li[now]; i != now; i = li[i])
            ret++;
    }

    ban[now] = true;
    return ret;
}

void SOLVE()
{
    while(t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> li[i],
            visited[i] = false,
            ban[i] = false;

        int cnt = 0;
        for(int i = 1; i <= n; i++)
            if(!visited[i]) cnt += DFS(i);
        cout << n - cnt << '\n';
    }
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

나를 포함해 TLE를 받은 대부분이 1번만 고려하여 문제를 해결했을 것이다.
최적화에 대해 다시 한 번 생각해볼 수 있었다.
Gold 상위 문제도 슥슥 톡 짠~ 하고 풀 수 있는 날이 오면 좋겠다.