[swea] 5643번 키순서 (java, dfs)

처음에 플로이드 와샬로 풀었는데 t의 자리에 tc를 넣었다가 런타임에러 났었다. 내일 다시 플로이드 와샬로 풀어봐야지 

 

내 위치에서 dfs로 돌면서 next(나보다 큰 친구들)의 count값을 증가시키면 next입장에서는 작은 애들의 개수만큼 

 

업데이트가 된다. temp는 dfs를 도는 횟수를 가르키는데 현재 내 번호보다 큰 친구들의 수(나 포함)로 count[내번호]+temp 해주면 나보다 큰 친구들의 수를 구할 수 있다. 

 

이렇게 temp로 업데이트 (나 포함해서 나보다 큰 친구들의 수) + count[next] 업데이트 (나보다 작은 친구수만큼 증가)

 

의 합이 n이 되면 나의 순서를 알 수 있는 경우이다.

 

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
	static int t,n,m;
	static ArrayList<Integer>[] big;
	static int[] count;
	static boolean[] vis;
	static int temp;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			m=sc.nextInt();
			big=new ArrayList[n+1];
			count=new int[n+1];
			for (int i = 1; i <n+1; i++) {
				big[i]=new ArrayList<>();
			}
			for (int i = 0; i < m; i++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				big[a].add(b);
			}
			
			
			for (int i = 1; i <=n; i++) {
				temp=0;
				vis=new boolean[n+1];
				dfs(i,i);
				count[i]+=temp;//나보다 큰 애들 
			}


			int total=0;
			for (int i = 1; i <=n; i++) {
//				System.out.print(count[i]+" ");
				if(count[i]==n)total+=1;
			}
			System.out.printf("#%d %d\n",tc,total);
			
		}
	}
	private static void dfs(int cur,int start) {
		temp+=1;
		for (int i = 0; i < big[cur].size(); i++) {
			int next=big[cur].get(i);
			if(vis[next])continue;
			vis[next]=true;
			count[next]+=1;//next보다 작은 친구들이 업데이트 해준다
			dfs(next,start);
		}
	}
}