SWEA - 키 순서 java

1) 2차원 배열에 나보다 크면 -1, 작으면 1로 표시한다. -> 반대로 표시해도 상관없음 

 

2) dfs처럼 나보다 크면 그 숫자로 파고들어간다 -> 파고들어갈수 있을때까지 간다 

3) 나보다 작은수도 2번과 같은 원리로 

4) 2), 3)에서 몇개의 숫자를 파고들수있는지 계산하고 그 합이 n-1이면 전체 정답+1 처리한다.

 

 

package a0406;

import java.util.*;
import java.io.*;

public class 키순서 {

	static int[][] arr ;
	static int[]visit;
	static int numcnt;
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			
			numcnt = Integer.parseInt(br.readLine());
			arr = new int[numcnt+1][numcnt+1];
			
			int comp = Integer.parseInt(br.readLine());
			for(int i=0; i<comp; i++) {
				StringTokenizer ST = new StringTokenizer(br.readLine(), " ");
				int num1 = Integer.parseInt(ST.nextToken());
				int num2 = Integer.parseInt(ST.nextToken());
				
				arr[num1][num2] = -1;
				arr[num2][num1] = 1;
			}
			
			int result = 0;
			
			for(int i=1; i<=numcnt; i++) {
				visit = new int[numcnt+1];
				int big = biggerfind(i);
				
				visit = new int[numcnt+1];
				int small = smallerfind(i);
				if(big+small==numcnt-1)result++;
				
				//System.out.println("nownum:"+i+" big:"+big+" small:"+small);
			}
			System.out.println("#"+t+" "+result);
		}
	}

	
	static int biggerfind(int num) {
		int cnt = 0;
		
		Queue<Integer>q = new LinkedList<>();
		q.add(num);
		visit[num] = 1;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			for(int i=1; i<=numcnt; i++) {
				if(visit[i]==0 && arr[now][i]==1) {
					q.add(i);
					visit[i] = 1;
					cnt++;
				}
			}
		}
		return cnt;
	}
	
	static int smallerfind(int num) {
		int cnt = 0;
		Queue<Integer>q = new LinkedList<>();
		q.add(num);
		visit[num] = 1;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			for(int i=1; i<=numcnt; i++) {
				if(visit[i]==0 && arr[now][i]==-1) {
					q.add(i);
					visit[i] = 1;
					cnt++;
				}
			}
		}
		return cnt;
	}
}