[백준 9466] 텀 프로젝트 (java)

문제보러가기

9466번: 텀 프로젝트

이 문제는 그래프 탐색 문제로 주어진 노드가 한 팀이 되는지 -> 사이클이 이뤄지는지 확인하는 문제였다.

dfs를 통해 풀이하였다.

 

 

 

 

 

 

 

문제풀이

처음에는 단순히 1번이 선택한 사람이 2번이면 1->2 이동후 2번이 선택한 사람 순으로 탐색을 진행하였다.

 

탐색을 진행하다가 start 한 1번이 다시 나오게 되면 사이클이 이뤄지므로 해당하는 사람들이 한 팀이고 이를 카운트 변수인 cnt에 담아 인원수를 판별하였는데 아래와 같은 경우의 반례가 존재했다.

 

이런 그래프의 경우 start가 1번이지만 2번까지 사이클이 형성되므로 2,3,4,5가 한 팀임에도 불구하고 팀이 아닌 것으로 나오게 된다.

 

 

따라서 나는 각 노드로 들어오는 방향(나를 선택한 번호 방향), 즉 반대방향으로 탐색을 진행하였다.

-선택받은 번호에 대해 List [] in에 저장한다.

-해당 번호로 들어오는 번호가 있다면 in [i]. size()!= 0 이면 탐색을 진행한다.

-방문한 번호는 visited [] 배열을 통해 체크하면서 넘어간다.

-그렇게 탐색해서 start번호로 오게 되면 사이클이 형성되었다고 판단.

-팀을 구성하지 못한 노드의 개수를 구하는 것이므로 전체 - 팀으로 구성된 노드의 개수가 답이 된다.

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int ans;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//텀 프로젝트 그래프 탐색
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int t = Integer.parseInt(br.readLine());
		while(t-- > 0) {
			ans=0;
			int n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());

			List<Integer>[] in = new List[n+1];
			boolean[] visited = new boolean[n+1];
			for(int i=0;i<=n;i++) {
				in[i] = new ArrayList<>();
			}
            //해당 번호의 노드로 들어오는 방향의 번호를 저장
			for(int i=1;i<=n;i++) {
				int num = Integer.parseInt(st.nextToken());
				 in[num].add(i);

			}
			for(int i=1;i<=n;i++) {
            	//해당 번호로 들어오는 노드가 없다면 사이클이 형성될 수 없음
				if(in[i].size()==0) {
					visited[i]=true;
					continue;
				}
            	//해당 번호로 들어오는 노드가 있다면 탐색
				if(!visited[i]) 
					dfs(i,i,in,visited,0);
			}
			bw.append(n-ans+"\n");
			
			
		}
		bw.flush();
	}
	static void dfs(int start,int num,List<Integer>[] in,boolean[] visited,int cnt) {
		//start노드번호로 다시 돌아온다면 팀원 수를 ans에 더해줌
		if(start==num && visited[num]) {
			ans+=cnt;
			return;
		}
        //이미 방문했던 노드라면 return
		if(visited[num])
			return;
		visited[num]=true;
        //들어오는 방향의 노드로 계속 탐색
		for(int i : in[num]) {
			if(!visited[i] || i==start)
				dfs(start,i,in,visited,cnt+1);
		}
	}

}