백준 9466 텀 프로젝트 Java

정답률 24퍼센트의 어려운 그래프 문제이다. '팀'프로젝트 인줄 알았는데

'텀'프로젝트였다. 이유는 모르겠다.

학생끼리 조를 짤 때 하고싶은 사람이 꼭 겹쳐야 조를 짤 수 있다.

한마디로 싸이클인 그래프에 속한 학생들만 조를 짤 수 있다는 것이다.

 

혼자하고 싶은 학생들은 자기 자신을 가리켜도 된다.

또는 마지막 학생이 가리킨 학생이 반드시 시작한 학생이여야 한다.

 

방문했는지를 확인하는 boolean형 배열 대신

int형 배열로 현재 정점이 몇 번째 방문한 정점인지 저장하고

또다른 int형 배열로 현재 정점이 어디서 부터 시작된 정점인 건지를 체크하고

확인하는 방식으로 문제를 풀면 된다.

 

 
import java.util.Scanner;
 
public class Q9466 {
    static int a[]; //입력받는 배열
    static int check[]; //방문 check(시작에서부터 몇번째로 방문되는 것인지)
    static int startVertex[];   //시작정점
     
    static int dfs(int i, int cnt, int start){
        
        if(check[i]!=0){ //이미 방문했던 정점이라면
            if(start!=startVertex[i]) //시작 정점과 같지 않은지 확인
                return 0;               //같지않다면 0리턴
            return cnt-check[i]; //같으면 몇번째 방문한 정점인지 리턴..
        }
         
        check[i]=cnt; //몇번째 방문한건지 저장 
        startVertex[i]=start; 
        return dfs(a[i],cnt+1, start); //가리키는 정점, +1번째 방문, start그대로 
    }
     
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int t=sc.nextInt();
         
        while(t-- > 0)
        {
            int n=sc.nextInt();
            a=new int[n+1];
            check=new int[n+1];
            startVertex=new int[n+1];
             
            for(int i=1;i<=n;i++)
                a[i]=sc.nextInt();
             
            int ans=0;
            for(int i=1;i<=n;i++){
                if(check[i]==0)
                    ans+=dfs(i,1,i);
            }
            System.out.println(n-ans);
         
        }
    }
}

예제에 있는 3 1 3 7 3 4 6 으로 설명해보자.

3은 자기 자신을 가리키기 때문에 생략하고

4 ->7 ->6 ->4 

4인경우

check[4] = 1

startVertex[4] = 1

4가 7을 가리키기 때문에 -> dfs(7, 2, 4)

check[7] = 2

startVertex[7] = 4

7이 6을 가리키기 때문에 ->dfs(6, 3, 4)

check[6] = 3

startVertex[6] = 4

6은 4를 가리키기 때문에 -> dfs(4, 4, 4)

이 때 if(check[i]!=0){ //이미 방문했던 정점이라면

            if(start!=startVertex[i]) //시작 정점과 같지 않은지 확인

                return 0;               //같지않다면 0리턴

            return cnt-check[i]; //같으면 몇번째 방문한 정점인지 리턴..

        }

조건문에 걸리게 된다.

cnt = 4 , check[4] = 1

4-1 = 3이므로 3명의 조원이 있는 것이다.

 

정답률이 낮은만큼 구현하는것도 그렇고 이해하기 조차 힘든 문제인 것 같다.