Baekjoon 9466: 텀 프로젝트

Problem Solving/BOJ

Baekjoon 9466: 텀 프로젝트

wrathlion 2024. 9. 15. 18:18

문제 정보

문제 링크
요약: Outdegree가 1인 그래프에서 cycle을 판별하고, cycle에 속하는 노드 구하기

Algorithm: `Graph`, `DFS`
난이도: Gold 3 ('24. 9. 15. 기준)
출처: solved.ac class 5 에센셜

풀이

가정: 학생들을 노드, 한 학생이 선택한 학생간의 관계를 방향이 있는 간선(directed edge)으로 하자.

접근 1

조건1: $n \le 10^5$
접근1: cycle이 되어야 한 팀이기 때문에 cycle 판별을 dfs로 naive하게 푼다면
- 모든 노드들에서 dfs를 수행하여 다른 노드들을 탐색
- 방문했던 노드를 또 방문한다면 cycle이 있는 것이고, 그 cycle에 속하는 학생들은 한 팀
- 제한: $O(n^2) = 10^5 \times 10^5$ = TLE
- 따라서 $O(n)$ or $O(n \log n)$ 인 솔루션이 필요할 듯 하다.

접근 2

조건2: 한 학생은 한 명의 학생만 선택하기 때문에 각 노드들은 outdegree가 1이다.
접근2: 위의 조건에 의해 두 노드 간의 경로는 유일하다!
- 위의 조건을 어떻게 사용할 수 있을까?
- 먼저 아래와 같은 $O(n)$ 가정을 하자
  - 가정: A에서 시작한 dfs와 이후 B에서 시작한 dfs는 독립적이지 않다
    - 즉, 이전 dfs 탐색에서 이미 한번 방문했던 노드들은 또 방문하지 않는다.
- 이런 상황에서 탐색 중 방문했던 노드를 만난다면 둘 중 한가지이다!
  - Case1: 이전 탐색에서 방문을 했거나
  - Case2: 현재 노드와 방문할 노드가 cycle에 속하거나
  - 위의 두가지 경우를 구분할 수 있는 방법은
    - 이번 탐색(dfs) 간 방문 했던 노드들을 저장하고
    - 다음 방문할 노드가 이미 방문되어있고, 방문 노드 리스트에 있다면
    - 다음 방문할 노드부터 현재 노드까지는 cycle이다.

검증

추론1: 두 노드 사이의 경로가 유일하기 때문에 한 cycle에 속하는 원소들은 다른 cycle에 속하지 않게 된다.
추론2: 한 탐색에서 이전 탐색이든, 이번 탐색이든 방문했던 노드에 도달했으면 더 이상 탐색을 진행시킬 이유가 없다.
- outdegree가 1개이기 때문에 방문했던 노드들이 갈 수 있는 노드들은 모두 방문했다.
- 방문 노드 리스트를 최대 1번 확인하고 탐색을 종료하니 $O(n)$으로 해결 가능하다.
추론3: 한 탐색에서 cycle을 확인한 노드는 다음 탐색 때 다시 확인할 필요가 없다.
- 위의 접근2-가정 이 틀린 가정이 아니라는 사실을 확인할 수 있다!

예시

1번에서 dfs를 시작 (1번 탐색)
- `1 -> 2 -> 3 -> 4` 순으로 탐색 진행 후
- 1번 노드를 만나고, 이는 이미 방문했던 노드임
- 따라서 방문 리스트를 확인하면 `[1, 2, 3, 4]`이고
- 1번 노드는 방문 리스트에 들어있기 때문에 1, 2, 3, 4번 노드는 cycle이다.
탐색이 끝난 뒤 2, 3, 4번 노드는 이전 탐색에서 방문했기 때문에 탐색 시작에서 무시
이후 5번으로 dfs를 시작 (2번 탐색)
- 1번 노드를 만나고, 이는 이미 방문했던 노드임
- 따라서 방문 리스트를 확인하면 `[5]`이고
- 1번 노드는 방문 리스트에 없기 때문에 5는 cycle에 속하지 않는다.

코드

main은 단순히 테스트케이스를 반복 + 빠른 입출력 설정하는 역할이라 solve, dfs 함수만 확인하면 된다

// Baekjoon09466.cpp
#include <iostream>

#include <vector>
#include <algorithm>

using namespace std;

vector<int> stck; // 이번 탐색 간 방문한 노드 리스트
int teamNum, teamInfo[100'001]; // 각 노드들의 팀 정보
int adjList[100'001]; // outdegree가 1이기 때문에 단순 배열로 선언
bool visited[100'001]; // 우리 모두가 아는 visited

void dfs(int curr) {
    visited[curr] = true;
    stck.push_back(curr);

    int next = adjList[curr];
    if (!visited[next])
        dfs(next);
    else {
        int nextIdx = 0;
        // 다음 방문할 노드가 방문 노드 리스트에 있는지 확인
        for (nextIdx = 0; nextIdx < stck.size() && stck[nextIdx] != next; nextIdx++);
        
        // 방문 노드 리스트에 존재하다면 cycle 체크
        if (nextIdx <= stck.size()) {
            for (; nextIdx < stck.size(); nextIdx++)
                teamInfo[stck[nextIdx]] = teamNum;
            teamNum++;
        }
    }

    stck.pop_back();
}

void solve() {
    int n;
    cin >> n;

	// 자원들이 테스트케이스마다 구분되지 않으므로 매번 초기화
    teamNum = 1;
    fill(visited, visited + n + 1, false);
    fill(teamInfo, teamInfo + n + 1, 0);

    for (int i = 1; i <= n; i++)
        cin >> adjList[i];

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

    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!teamInfo[i])
            ans++;

    cout << ans << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

잡담

SCC 느낌도 나는 굉장히 재밌는 신박한 문제였다.

outdegree가 1인 그래프에서는 $O(n)$으로 cycle detection을 할 수 있다는 점이 신기하기도 했다.

만약 한 노드의 outdegree가 1보다 크다면, 위의 방법으로 cycle에 속하는 원소들을 구할 수 없다.

(직접 해보면 된다!)

즉, 일반적인 graph의 cycle 판별이 아니라는 것!

특수한 경우이기 때문에 이 문제를 시간 안에 풀 수 있었음

풀이를 생각해내는 것보다 풀이를 남들이 이해가 되도록 글로 쓰는 것은 굉장히 어려운 작업이라는 것을 다시 한번 느꼈다.

거기다가 틀린 풀이가 아니라는 것을 생각해 내는 것 또한 어려웠다!

물론 틀린 풀이거나 틀린 부분이 있다면 알려주세요!

사이클 판별이라 Union-Find 인가 했지만 detection 뿐만 아니라 노드들을 탐색해야하므로 적절하지 못하다고 생각했다.