[알고리즘] Java / SWEA / 키 순서 / 5643

[알고리즘] Java / SWEA / 키 순서 / 5643

문제

문제 링크

접근 방식

n번째 학생보다 키가 작은 모든 학생을 구하기 위해서는 문제 예시 그림의 화살표 방향으로 탐색하면 된다

n번째 학생보다 키가 큰 모든 학생을 구하기 위해서는 화살표 반대 방향으로 탐색한다

따라서 키가 작은 방향으로 연결된 그래프와 큰 방향으로 연결된 그래프 두 개로 dfs 탐색하여 모든 학생이 탐색되면 카운팅한다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_5643 {

	/* 아이디어
	 * n번째 학생에 대해
	 * n번째 학생보다 키가 작은 모든 학생을 구하기 위해서는 문제 예시 그림의 화살표 방향으로 탐색하면 된다
	 * n번째 학생보다 키가 큰 모든 학생을 구하기 위해서는 화살표 반대 방향으로 탐색한다
	 * 따라서 키가 작은 방향으로 연결된 그래프와 큰 방향으로 연결된 그래프 두 개로 dfs 탐색하여 모든 학생이 탐색되면 카운팅한다
	 */
	
	static boolean visited[];
	static int N;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		for(int tc=1;tc<=T;tc++) {
			N = Integer.parseInt(br.readLine());
			int M = Integer.parseInt(br.readLine());
			
			boolean[][] toSmall = new boolean[N+1][N+1];
			boolean[][] toBig = new boolean[N+1][N+1];
			
			for(int i=0;i<M;i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				toSmall[a][b] = true;
				toBig[b][a] = true;
			}
			
			int answer = 0;
			for(int i=1;i<=N;i++) {
				visited = new boolean[N+1];
				dfs(i,toSmall);
				dfs(i,toBig);
				
				int cntVisited = 0;
				for(int j=1;j<=N;j++) {
					if(visited[j])cntVisited++;
				}
				
				if(cntVisited==N)answer++;
			}	
			sb.append("#"+tc+" "+answer+"\n");
		}
		System.out.print(sb);
	}
	
	public static void dfs(int node,boolean[][] connect) {
		visited[node] = true;
		
		for(int i=1;i<=N;i++) {
			if(connect[node][i] && !visited[i]) {
				dfs(i,connect);
			}
		}
	}

}