백준 9466:텀 프로젝트

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

백준 9466번 문제예요. 이번 문제를 풀면서 자신이 얼마나 무력한지 깨달았습니다.

이번 문제도 탐색하는 문제였는데요. 이전 문제들과는 달리 재귀함수가 필요한가? 라고 생각했습니다. 단방향 그래프문제기 때문에 백트래킹이 필요없다고 생각했어요. 그래서 그냥 사이클이 발견될때마다 크기를 체크해서 리턴하는 방식으로 코딩했습니다. 그리고 탐색할때마다 방문체크배열을 초기화하면 시간초과가 뜨더라구요.. 그래서 방문체크배열과 완전히탐색이 끝난배열 총 2개를 이용해서 풀었습니다.

밑에는 제 코드입니다.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
 
#define MAX 100005
 
int graph[MAX];  //그래프
bool visited[MAX];  //방문체크
bool checked[MAX];  //탐색이 끝났는지 체크
int students;  //학생 수
int cnt1;  //팀원이 되지 못한 학생 저장용
 
int dfs(int cur) {
    int i,cnt=0;
    for (i = cur; !visited[i]; i = graph[i]) {  //현재 위치부터 이동하면서 방문
        visited[i] = true;  //방문 했다고 체크
    }
    if (i == cur) {  //현재 위치에서 사이클이 발견된 경우
        for (int k = i; !checked[k]; k = graph[k]) {  //사이클 탐색이 끝날 때 까지
            checked[k] = true;                          //사이클의 크기 
            cnt++;
        }
        return cnt;  //사이클의 크기 리턴
    }
    else {  //현재 위치가 사이클에 포함이 안된 경우
        for (int k = cur; k != i; k = graph[k]) {  //사이클의 시작지점까지 탐색완료 체크
            checked[k] = true;
        }
        return 0;
    }
}
 
int main(void) {
    int T;
    scanf("%d", &T);
    for (int testCase = 0; testCase < T; testCase++) {
        scanf("%d", &students); cnt1 = students;  //총 학생수 저장
        for (int i = 0; i < students; i++) {
            int st;
            scanf("%d", &st);
            graph[i] = st - 1;    //0을 시작으로 했어요
        }
        for (int i = 0; i < students; i++) {
            int cnt = dfs(i);
            if (cnt) {  //사이클이 발견되면
                cnt1 -= cnt;  //총 학생 수에서 사이클의 크기를 빼요
            }
        }
        printf("%d\n", cnt1);
        for (int i = 0; i < students; i++) {  //testCase가 끝나면 초기화
            visited[i] = false;
            checked[i] = false;
        }
    }
    
 
    return 0;
}

*새로운 코드 추가(2020. 1. 30)