알고리즘
[C++] Boj 9466 텀 프로젝트
(ꐦ •᷄ࡇ•᷅)
2025. 1. 8. 21:48
문제 링크
접근
문제를 읽고 사이클을 구하면 되는 문제인 걸 알아챘으나 사이클을 어떻게 찾는지는 몰라서 풀지 못했다. 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번 학생 탐색 시작
- visited[1] = true로 표시.
- students[1] = 2이므로 2번으로 이동.
- DFS 재귀 호출로 2번 탐색.
2번 학생 탐색
- visited[2] = true로 표시.
- students[2] = 3이므로 3번으로 이동.
- DFS 재귀 호출로 3번 탐색.
3번 학생 탐색
- visited[3] = true로 표시.
- students[3] = 1이므로 1번으로 이동.
- 1번은 이미 visited[1] == true이며, done[1] == false이므로 사이클 발견.
- 사이클 내부 노드(1, 2, 3)를 카운트(cnt += 3).
- DFS 호출이 끝나면서 탐색 완료 표시:
done[3] = true;
done[2] = true;
done[1] = true;