[BOJ] 2458. 키 순서 - java (SWEA_5643)

⬛ [BOJ] 2458. 키 순서 - java

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

2458번: 키 순서

⬛ 풀이 방법

• 인접 행렬을 만들고 방향있는 간선 사용
• 나보다 작은 학생들에 대한 정보와 나보다 큰 학생들에 대한 정보의 합이 N-1개면 나의 키가 몇번째인지 알 수 있다.
• BFS를 이용하여 주어진 정보에서 더 알아낼 수 있는 정보를 추가
• 학생별로 count 배열을 만들어 나보다 작은 학생들에 대한 정보나 큰 학생들에 대한 정보를 알 때마다 +1

⬛ 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_2458_키순서 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] input = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int M = Integer.parseInt(input[1]);

		int result = 0;
		Queue<int[]> queue = new LinkedList<>();
		int[][] matrix = new int[N + 1][N + 1]; // 1 ~ N까지
		int[] count = new int[N + 1];
		for (int i = 0; i < M; i++) {
			input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);
			matrix[a][b] = 1;
			count[a]++; // 원소보다 큰 것에 대한 정보를 알 수 있을 때
			count[b]++; // 원소보다 작은 것에 대한 정보를 알 수 있을 때
			queue.add(new int[] { a, b }); // a<b
		}
		while (!queue.isEmpty()) { // bfs
			int[] cur = queue.poll();

			for (int i = 1; i <= N; i++) {
				// 현재 원소에서 i에 대해 아직 체크가 안되어 있고 현재 원소보다 큰 원소인 cur[1]보다 큰 i가 있으면 현재 원소보다 i가 더 크므로 체크
				if (matrix[cur[0]][i] != 1 && matrix[cur[1]][i] == 1) {
					matrix[cur[0]][i] = 1;
					count[cur[0]]++; // 원소보다 큰 것에 대한 정보를 알 수 있을 때
					count[i]++; // 원소보다 작은 것에 대한 정보를 알 수 있을 때
					queue.add(new int[] { cur[0], i });
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			if (count[i] == N - 1) { // 각 원소보다 크거나 작은 원소에 대한 정보를 카운트한게 N-1개면 자신의 키가 몇번째인지 알 수 있다.
				result++;
			}
		}
		System.out.println(result);
	}
}