백준 9466번 C++ 텀 프로젝트

텀 프로젝트

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

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

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

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

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

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

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

시간 초과, 메모리 초과

이 문제의 꽃은 시간 초과이다.

문제 자체는 크게 어렵진 않다고 생각했지만

그렇게 해서 고친 코드는

교회를 뛰쳐나온지 어언 10년... 이럴 때마다 내가 교회를 뛰쳐나왔기 때문에 시험에 드는 게 아닌지 생각이 든다.

뭐 무턱대고 그냥 돌려봤다. 그 뒤로 그리고 시초 메초 틀 시초... 전리품이 하나씩 늘어서 너무 빡쳤던 것이다.

게시판을 뒤지며 알아낸 시간 초과 해결 방법은 싸이클에 들어가는 노드를 체크해주는 것이었다.

그리고나서 작성한 코드가 다음과 같다.

처음 코드는 시간초과 날 거라는 걸 알면서도 돌리긴 했다... 항상 시간 초과 보고 나서야 정신을 차리는데

처음부터 효율적인 코드를 고민하는 습관을 들여야겠다.

메모리초과 알아내는 반례는 다음과 같다.

1
5
2 3 4 5 4

코드

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
int graph[MAX], n;
int check[MAX]={0,};
vector<int> v;
void dfs(int start){
    v.push_back(start);
    int next=graph[start];
    if(check[next]!=0){
        if(v.front()!=next)
            graph[v.front()]=-1;
        int len=check[next];
        while(v.size()>=len){
            check[v.back()]=0;
            graph[v.back()]=0;//이미 사이클 포함
            v.pop_back();
        }
        while(!v.empty()){
            check[v.back()]=0;
            v.pop_back();
        }
        return;
    }
    if(graph[next]==0||graph[next]==-1){//이미 사이클이 형성된 곳이나 불가능한 곳
        graph[v.front()]=-1;
        while(!v.empty()){
            check[v.back()]=0;
            v.pop_back();
        }
        return;
    }
    check[next]=check[start]+1;
    dfs(next);
}
int main() {
    int T;
    scanf("%d", &T);
    while(T>0){
        scanf("%d", &n);
        for(int i=1; i<=n; i++){
            scanf("%d", &graph[i]);
        }
        for(int i=1; i<=n; i++){
            if(graph[i]==0)
                continue;
            check[i]=1;
            dfs(i);
        }
        int cnt=0;
        for(int i=1; i<=n; i++){
            if(graph[i]==-1)
                cnt++;
        }
        printf("%d\n", cnt);
        T--;
    }
    return 0;
}
 

이거 못 풀었으면 내일 오카야마 여행 내내 생각났을 것 같다.

메모리랑 시간 줄일 수 있는 방법을 찾아봐야할 듯하다...