[백준/BOJ] 9466번 텀 프로젝트 (C++)

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

BFS로 풀다가 시간 초과 때문에 2시간 날린 문제 ... (다시 풀기)

 

lmcoa15.tistory.com/51

백준 9486번 - 텀 프로젝트

결국 구글링으로 찾아본 결과 대부분 백트래킹 + DFS로 푼 것 같았다. (위는 풀이를 아주 자세히 해주어서 보면 도움이 될 것 같습니다.) 포인트는 다음과 같습니다.

 

1. 각각의 학생을 방문 했는가?

2. 몇번을 방문 했는가?

3. 방문할 때 처음 시작했던 학생의 번호가 무엇인가?

 

1번, 2번은 visit 배열을 선언한 후, 학생을 방문할 때 마다 방문 횟수를 저장하는 변수 cnt를 둬서 저장해줍니다. 

3번은 first 배열을 선언하여, 시작 번호를 저장해줍니다.

 

이를 통해 사이클이 발생했을 때 문제에 대한 예외처리를 적절하게 할 수 있게 됩니다.

 

#include <iostream>
#include <cstring>
#define MAX 100001
using namespace std;

int T, n;
int student[MAX]; // 학생이 가리키는 다른 학생 번호를 저장
int first[MAX]; // 처음으로 DFS를 시작하는 번호를 저장
int visit[MAX]; // 방문 유무 및 횟수 저장

int DFS(int start, int now, int cnt) {
    // 방문했던 학생인 경우
    if(visit[now]) {
        // 이전에 사이클이 생성된 경우
        if(first[now] != start) return 0;
        // 현재 생성된 사이클에 해당하는 학생 수
        return cnt - visit[now];
    } else {
        first[now] = start;
        visit[now] = cnt;
        return DFS(start, student[now], cnt + 1); // 시작 번호, 다음 번호, 방문 횟수
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--) {
        int answer = 0;
        memset(first, 0, sizeof(first));
        memset(visit, 0, sizeof(visit));
        cin>>n;
   
        for(int i = 1; i <= n; i++) {
            cin>>student[i];
        }
        
        for(int i = 1; i <= n; i++) {
            if(!visit[i]) {
                answer += DFS(i, i, 1); // 시작 번호, 현재 번호, 방문 횟수
            }
        }
        
        cout<<n - answer<<"\n"; // 전체 학생 수 - 사이클에 해당하는 학생 수
    }
}