[SWEA-5643] 키 순서

이 문제는 SWEA professional 키 순서 라는 문제이다.

 

 

개인적으로 접근이 어려웠던 문제였다.

그래프를 쓰면 되겠다는 건 알았는데, 도대체 어떻게 활용해야 할 지 감이 잘 안왔다.

 

선생님께서 방법을 알려주셨는데,

 

1) 정보들을 인접행렬에 넣기

2) 나보다 작은 애들 찾기

3) 나보다 큰 애들 찾기

4) 나보다 작은애 + 큰 애 = 전체 학생수 -1 이면 내 키 번호 알 수 있음

 

이 로직으로 풀면 된다.

사실 뭔가... 혼자 엄청 헤메고 있었는데 생각보다 간단한 문제인 걸 알고 놀랐다.

더 연습해야겠따..

 

package hw_0421;

import java.util.Scanner;

public class 키순서 { //SWEA D4
	static int N,M, ans, tcnt, scnt;
	static int[][] map;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			N = sc.nextInt(); //학생 수
			M = sc.nextInt(); //비교 횟수
			
			map = new int[N+1][N+1];
			ans = 0;
			
			for(int i=0; i<M; i++) {
				int from = sc.nextInt();
				int to = sc.nextInt();
				map[from][to] = 1;
			}
			
			for(int i=1; i<N+1; i++) {
				tcnt = 0;
				scnt = 0;
				taller(i, new boolean[N+1]);
				shorter(i, new boolean[N+1]);
				if(tcnt + scnt == N-1)
					ans++;
			}
			
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void taller(int from, boolean[] visited) {
		visited[from] = true;
		for(int i=1; i<N+1; i++) {
			if(!visited[i] && map[from][i] == 1) {
				taller(i, visited);
				tcnt++;
			}
		}
	}
	static void shorter(int to, boolean[] visited) {
		visited[to] = true;
		for(int i=1; i<N+1; i++) {
			if(!visited[i] && map[i][to] == 1) {
				shorter(i, visited);
				scnt++;
			}
		}
	}
}