[BaekJoon] 2458 키 순서 (Java)

1.  문제 링크

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

2.  문제

요약

• 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어집니다.
• N명의 학생들의 키는 모두 다르다고 가정합니다.
• 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있을 수 있습니다.
• a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려 그래프로 표현할 수 있습니다.
• 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 500보다 작거나 같은 학생들의 수 N과 0보다 크거나 같고 N(N - 1) / 2보다 작거나 같은 두 학생 키를 비교한 횟수 M이 주어지고 두 번째 줄부터 M개의 줄에 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어집니다. 번호가 a인 학생이 번호가 b인 학생보다 키가 작다는 것을 의미합니다.
• 출력: 첫 번째 줄에 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static ArrayList<Edge>[] map;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		map = new ArrayList[N + 1];
		for(int stu = 1; stu <= N; stu++) map[stu] = new ArrayList<>();
		for(int edge = 0; edge < M; edge++) {
			int small = scanner.nextInt(), big = scanner.nextInt();
			map[small].add(new Edge(big, 1));
		}
	}
	
	static void solution() {
		int[][] distance = new int[N + 1][N + 1];
		for(int stu = 1; stu <= N; stu++) dijkstra(stu, distance[stu]);
		int stuNum = 0;
		for(int stu = 1; stu <= N; stu++) {
			boolean flag = false;
			for(int other = 1; other <= N; other++) {
				if(distance[stu][other] == Integer.MAX_VALUE && distance[other][stu] == Integer.MAX_VALUE) {
					flag = true;
					break;
				}
			}
			if(!flag) stuNum++;
		}
		System.out.println(stuNum);
	}
	
	static void dijkstra(int start, int[] dist) {
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		Queue<Edge> queue = new LinkedList<>();
		queue.offer(new Edge(start, 0));
		while(!queue.isEmpty()) {
			Edge cur = queue.poll();
			if(dist[cur.node] < cur.weight) continue;
			for(Edge e : map[cur.node]) {
				if(dist[e.node] > dist[cur.node] + e.weight) {
					dist[e.node] = dist[cur.node] + e.weight;
					queue.offer(new Edge(e.node, dist[e.node]));
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Edge {
		int node, weight;
		public Edge(int node, int weight) {
			this.node = node;
			this.weight = weight;
		}
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {					
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4. 접근

• 키가 작은 사람으로부터 키가 큰 사람으로 가는 화살표를 이용하여 그래프를 만듭니다.
• 모든 사람에 대해 다익스트라 알고리즘을 이용하여 다른 모든 사람까지의 최단 거리를 구하고 이를 이차원 배열에 1번 학생부터 N번 학생까지 저장합니다.
• 각 학생에 대해 이차원 배열에서 행에 있는 값과 열에 있는 값을 각각 확인하여 자신보다 큰 사람과 작은 사람이 누구인지를 확인하고 모든 학생에 대해 자신보다 키가 큰지 작은지 확인할 수 있다면 정답에 1을 추가합니다.
  • 행에는 해당 학생을 기준으로 다익스트라 알고리즘을 이용한 다른 모든 사람까지의 최단 거리가 들어있습니다.
  • 그래프를 만들 때 자신보다 큰 사람에게만 이동할 수 있는 단방향 그래프를 만들었기 때문에 다익스트라 결과에서 최단 거리를 구한 부분은 자신보다 큰 학생임을 의미합니다.
    
    
  • 열에는 다른 학생들로부터 해당 학생에게까지의 최단 거리가 적혀있습니다.
  • 즉, 최단 거리를 구한 부분의 학생은 해당 학생보다 키가 작은 학생임을 의미합니다.
    
    
  • 그렇기 때문에 행과 열을 보고 해당 문제의 답을 구할 수 있습니다.