Code up 4714 BAEKJOON 2458 키 순서

  Ex) 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

  - 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다.

  - 단, N명의   학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

  - 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 

  - 1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 

  - 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다.

  - 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다. 

  - 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

  - 첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 

  - 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다.

  - 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

 

 

<hide/>
/*

6 6
1 5
3 4
5 4
4 2
4 6
5 2

 */
import java.util.Scanner;
public class HeightOrder {
	static int MAX_COUNT = 501;
	static int [][] AdjMatrix = new int[MAX_COUNT][MAX_COUNT];
	static int[] VisitMatrix = new int[MAX_COUNT];
	static int VertaxCnt, EdgeCnt;
	static int cnt;
	
	public static void main(String[] args) {
		int sum = 0, PersonCnt = 0;
		Scanner scan = new Scanner(System.in);
		VertaxCnt = scan.nextInt();
		EdgeCnt = scan.nextInt();
		
		for(int i = 1; i <= EdgeCnt; ++i) {
			int V1 = scan.nextInt();
			int V2 = scan.nextInt();
			AdjMatrix[V1][V2] = 1;
		}
		
		for(int i = 1; i <= VertaxCnt; ++i) {
			DFS1(i);	//	 i -> curr
			sum += cnt;
			cnt = 0;
			for(int j = 1; j <= VertaxCnt; ++j ) {
				VisitMatrix[j] = 0;
			}
			DFS2(i);		// curr -> i
			sum += cnt;
			cnt = 0;
			if(VertaxCnt - 1 == sum ) {
				++PersonCnt;
			}
			for(int j = 1; j <= VertaxCnt; ++j) {
				VisitMatrix[j] = 0;					
			}
			sum = 0;
		}
		System.out.println(PersonCnt);
	}
	
	public static void DFSmethod(int _CurrV1, int _CurrV2) {
		
		VisitMatrix[_CurrV2] = 1;
		for(int i = 1; i <= VertaxCnt; ++i) {
			if(0 == VisitMatrix[i] && 1 == AdjMatrix[_CurrV2][i] ) {
				++cnt;
				System.out.printf("(%d->%d) -> (%d, %d)\n" ,_CurrV1, _CurrV2, _CurrV2, i);
				DFSmethod(_CurrV2, i);
			}
		}
	}

	public static void DFS1(int _CurrVertax){
		VisitMatrix[_CurrVertax] = 1;
		for(int i = 1; i <= VertaxCnt; ++i) {
			if(0 == VisitMatrix[i] && 1 == AdjMatrix[_CurrVertax][i]) {
				++cnt;
				DFS1(i);
			}
		}
	}
	
	public static void DFS2(int _CurrVertax){
		VisitMatrix[_CurrVertax] = 1;
		
		for(int i = 1; i <= VertaxCnt; ++i ) {
			if(0 == VisitMatrix[i]  && 1 == AdjMatrix[i][_CurrVertax]) {
				++cnt;
				DFS2(i);
			}			
		}
	}
}

 

 

  Note) 입출력 코드

<hide/>

입력
6 6
1 5
3 4
5 4
4 2
4 6
5 2

출력
1


입력
10 40
3 6
7 10
6 2
3 2
1 8
9 2
1 3
5 6
8 4
2 4
1 10
1 2
7 3
9 6
5 4
7 5
9 3
5 3
8 2
10 6
6 4
7 4
5 2
9 4
7 1
7 6
9 8
7 9
1 5
1 4
7 8
3 4
7 2
10 5
1 6
9 10
10 3
9 5
8 3
9 1

출력
7

  - 나보다 큰 친구들 카운트하는 DFS1, 나보다 키 작은 친구를 카운트하는DFS2 두 개를 만든다.

  - 문제에서 주어진대로 최댓값 MAX_COUNT를 적용해서 501로 잡는다.

  - DFS1을  실행한 다음 VisitMatrix를 0으로 초기화 시틴다.

  - DFS2를 실행한 다음에는 나보다 작은 친구와 나보다 큰 친구를 더한 값인 sum이 VertaxCnt - 1 과 같을 때,

    -> PersonCnt를 플러스한다.

    -> VertaxCnt - 1: 정점의 개수에서 나를 제외한 값

  - PersonCnt를 한 다음에 또 다시 방문행렬과 sum을 0으로 초기화시킨다. 

 

 

 출처: https://www.acmicpc.net/problem/2458

2458번: 키 순서

 https://codeup.kr/problem.php?id=4714