[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트

DFS 를 이용해서 사이클을 이루는지 확인하는 문제

 

사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다..

결과는 시간초과!

틀린 코드

#include <bits/stdc++.h>

using namespace std;

int student[100001];
bool visited[100001];

int makeUnion(int st, int p){
    if(student[p] == st) return student[p] = 0;
    return student[p] = makeUnion(st, student[p]);
}

void dfs(int st, int now, int& cnt){
    // 방문한 곳에 또 방문했다는 것은 now에서 사이클이 존재한다는 말
    // 마지막 원소만 자기 자신을 찍은 경우는 O(n^2)이 된다..
    if(!student[now]){
        cnt++;
        return;
    }
    if(visited[now]){
        makeUnion(now, now);
        if(st == now) return;
        else{
            cnt++;
            return; 
        }
    }
    
    visited[now] = true;
    dfs(st, student[now], cnt);
    visited[now] = false;
}

int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        int sn, cnt = 0, start;
        cin >> sn;
        for(int i = 1; i <= sn; i++){
            cin >> student[i];
        }
        for(int i = 1; i <= sn; i++){
            if(!student[i]) continue;
            dfs(i, i, cnt);
            student[i] = 0;
        }
        cout << cnt << "\n";
    }
    return 0;
}

확실히 팀을 찾았는지 체크를 하기 위해서 check 배열을 하나 더 만들어 주었다!

visitied배열만으로는 현재 dfs 루프에서 방문여부만 알 수 있고 팀이 이루어 졌는지는 student 배열을 모두 돌아봐야지만 알 수 있기 때문

 

dfs를 하면서 visited 배열 이외에 추가적인 배열을 사용해서 방문 여부를 컨트롤 해본건 처음이었다..

새로운 방법이 있다는 걸 알려준 아주 고마운 문제!!

#include <bits/stdc++.h>
 
using namespace std;
 
int N, student[100001], result;
bool visited[100001];   
bool check[100001]; // 인덱스에 해당하는 학생이 팀을 이루었는지 확인하는 배열
 
void dfs(int now, int& res){
    visited[now] = true;
    int next = student[now];
    
    if(!visited[next]) dfs(next, res);  // 만약 다음 학생을 방문하지 않았다면 go
    else if(!check[next]){      // next에 방문을 했고, 아직 팀을 이루는지 확인하지 못했다면 
        // next가 사이클의 시작이 되고, 자기 자신에게 돌아올 때까지 res++
        for(int i = next; i != now; i = student[i]){
            res++;
        }
        res++;  // 자기자신
    }
    // now가 팀을 이루는지 확인했으므로 true
    check[now] = true;
}
 
int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        memset(visited, false, sizeof(visited));
        memset(check, false, sizeof(check));
        int sn, res = 0;    // res : 사이클을 이루는 학생 수
        cin >> sn;
        for(int i = 1; i <= sn; i++){
            cin >> student[i];
        }
        
        for(int i = 1; i <= sn; i++){
            if(!visited[i]) dfs(i, res);
        }
        cout << sn - res << "\n";
    }
    return 0;
}