[C++] Boj 9466 텀 프로젝트

문제 링크

9466 텀 프로젝트

 

접근

문제를 읽고 사이클을 구하면 되는 문제인 걸 알아챘으나 사이클을 어떻게 찾는지는 몰라서 풀지 못했다. DFS로 풀면 될 것 같았는데, 어찌저찌 해 보다가 8 %에서 막혔다.

사이클 찾는 문제도 dfs, bfs처럼 약간 공식 같은 무언가가 있을 것 같아서 찾아보았다.

---

done 배열

먼저 visted, map과 더불어 done 배열이 새로 등장하였다. 이 done 배열은 해당 노드들이 사이클이 맞는지 체크하는 배열이었다.

이 방법을 활용하여 문제를 다시 풀어보았다.

---

코드

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100000 + 1;

int n, cnt;
int students[MAX];
bool visited[MAX];
bool done[MAX];

void dfs(int index)
{
    visited[index] = true;

    int next = students[index];
    if (!visited[next])
        dfs(next);
    else if (!done[next])
    {
        for (int i = next; i != index; i = students[i])
            cnt++;
            
        // 자기 자신
        cnt++;
    }

    done[index] = true;
}

int main()
{
    int T;
    cin >> T;

    for (int i = 0; i < T; i++)
    {
        memset(visited, false, sizeof(visited));
        memset(done, false, sizeof(done));
        cin >> n;

        for (int j = 1; j <= n; j++)
            cin >> students[j];

        cnt = 0;

        for (int j = 1; j <= n; j++)
        {
            if (!visited[j])
                dfs(j);
        }

        cout << n - cnt << '\n';
    }

    return 0;
}

---

중요하다고 생각하는 것

    else if (!done[next])
    {
        for (int i = next; i != index; i = students[i])
            cnt++;
            
        // 자기 자신
        cnt++;
    }

 

위 for loop가 사이클을 찾는 핵심 방식이라고 생각한다.

• 다음 학생이 이미 방문되었지만 탐색 완료(done)되지 않은 경우, 사이클을 발견한 것이다.
  • 왔던 곳을 다시 왔으니까 visited는 true인데, done은 false인 것 이용.
• 사이클 내부에 포함된 학생들을 for 루프를 통해 카운트한다.
  • i = next에서 시작하여 사이클을 순회하며 cnt를 증가시킨다.
  • 마지막으로 자기 자신도 포함한다(cnt++).

---

done의 역할

특정 노드(index)의 탐색이 완료되었음을 나타낸다.즉, index와 관련된 모든 경로 탐색이 끝났으므로, 다시 탐색할 필요가 없음을 표시한다.

예시: 1 → 2 → 3 → 1 (사이클)

초기 상태

• visited: 모든 값이 false.
• done: 모든 값이 false.

1번 학생 탐색 시작

1. visited[1] = true로 표시.
2. students[1] = 2이므로 2번으로 이동.
3. DFS 재귀 호출로 2번 탐색.

2번 학생 탐색

1. visited[2] = true로 표시.
2. students[2] = 3이므로 3번으로 이동.
3. DFS 재귀 호출로 3번 탐색.

3번 학생 탐색

1. visited[3] = true로 표시.
2. students[3] = 1이므로 1번으로 이동.
3. 1번은 이미 visited[1] == true이며, done[1] == false이므로 사이클 발견.
4. 사이클 내부 노드(1, 2, 3)를 카운트(cnt += 3).
5. DFS 호출이 끝나면서 탐색 완료 표시:

done[3] = true;
done[2] = true;
done[1] = true;

---

참고 링크

https://jaimemin.tistory.com/674