백준 9466번

텀 프로젝트

Posted by ChoiCube84 on January 13, 2024 · 11 mins read

백준 9466번

오늘 풀어본 문제는 백준의 9466번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이 $(s_1, s_2, …, s_r)$ 이라 할 때, $r=1$ 이고 $s_1$ 이 $s_1$ 을 선택하는 경우나, $s_1$ 이 $s_2$ 를 선택하고, $s_2$ 가 $s_3$ 를 선택하고,…, $s_{r-1}$ 이 $s_r$ 을 선택하고, $s_r$ 이 $s_1$ 을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 $7$ 명의 학생이 있다고 하자. 학생들을 $1$ 번부터 $7$ 번으로 표현할 때, 선택의 결과는 다음과 같다.

1 2 3 4 5 6 7
3 1 3 7 3 4 6

위의 결과를 통해 $(3)$ 과 $(4, 7, 6)$ 이 팀을 이룰 수 있다. $1, 2, 5$ 는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 $n$ $(2 \le n \le 100,000)$ 으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 $1$ 부터 $n$ 까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

풀이과정

1번째 시도

문제를 해결하기 위해 떠올린 방법은 각 학생의 번호를 정점으로 하고 각각의 선택을 방향이 있는 간선으로 하는 그래프를 구성한 뒤, DFS를 이용하여 어떤 정점에서 출발하여 자기 자신으로 돌아올 수 있는지를 검증하는 것이었다.

또한 시간이 너무 오래 걸릴 것을 염두에 두고, 탐색 과정에서 어떤 정점에서 자기 자신으로 되돌아 올 수 있는 것이 확인되면 해당 루프의 모든 정점도 각각 자기자신으로 되돌아 올 수 있기 때문에, 이를 저장해두도록 하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

void simulate();
void search(int start, const vector<int>& graph, vector<int>& result);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate() {
    int n, alone = 0;
    cin >> n;

    vector<int> graph(n+1, 0);
    vector<int> result(n+1, 0);

    for (int i=1; i<=n; i++) {
        cin >> graph[i];
    }

    for (int i=1; i<=n; i++) {
        if (result[i] == 0) {
            search(i, graph, result);
        }
    }

    for (int i=1; i<=n; i++) {
        if (result[i] == -1) {
            alone++;
        }
    }

    cout << alone << "\n";
}

void search(int start, const vector<int>& graph, vector<int>& result) {
    int n = result.size() - 1;
    vector<bool> visited(n + 1, false);

    int curr = start;

    while (!visited[curr] && result[curr] == 0) {
        visited[curr] = true;
        curr = graph[curr];
    }

    if (curr == start) {
        for (int i=1; i<=n; i++) {
            if (visited[i]) {
                result[i] = 1;
            }
        }
    }
    else {
        result[start] = -1;
    }
}

실행 결과 ‘시간 초과’ 가 떴다.

2번째 시도

시간 초과의 원인으로 알아낸 것은, 루프를 형성하지 못하는 정점들이 여러 번 확인되는 것이었다. 자기 자신으로 되돌아올 수 없는 정점들도 바로 저장하도록하여 시간 초과 해결을 시도하였다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

void simulate();
void search(int start, const vector<int>& graph, vector<int>& result);

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int i=0; i<T; i++) {
        simulate();
    }

    return 0;
}

void simulate() {
    int n, alone = 0;
    cin >> n;

    vector<int> graph(n+1, 0);
    vector<int> result(n+1, 0);

    for (int i=1; i<=n; i++) {
        cin >> graph[i];
    }

    for (int i=1; i<=n; i++) {
        if (result[i] == 0) {
            search(i, graph, result);
        }
    }

    for (int i=1; i<=n; i++) {
        if (result[i] == -1) {
            alone++;
        }
    }

    cout << alone << "\n";
}

void search(int start, const vector<int>& graph, vector<int>& result) {
    int n = result.size() - 1;
    vector<bool> visited(n + 1, false);

    int curr = start;

    while (!visited[curr] && result[curr] == 0) {
        visited[curr] = true;
        curr = graph[curr];
    }

    if (curr == start) {
        result[start] = 1;
        for (curr = graph[start]; curr != start; curr = graph[curr]) {
            result[curr] = 1;
        }
    }
    else {
        result[start] = -1;
        for (int fail = graph[start]; fail != curr; fail = graph[fail]) {
            result[fail] = -1;
        }

        if (result[curr] == 0) {
            start = curr;
            result[start] = 1;
            for (curr = graph[start]; curr != start; curr = graph[curr]) {
                result[curr] = 1;
            }
        }
    }
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

길고 긴 여정 끝에, 드디어 CLASS 5 를 달성하였다!!!

CLASS 5

그러나 본 게임은 지금부터가 될 것이다. 이제 CLASS 5의 모든 에센셜 문제를 푼 뒤, 최종적으로 군입대 전까지 CLASS 5 MASTER 에 도달할 수 있도록 최선을 다해야 할 것이다.

오늘의 PS는 여기까지!


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