백준 2458: 키 순서

문제 요약

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• 최단 경로
• 플로이드-워셜

문제 풀이

dfs 방식으로 먼저 풀었다가, 시간이 너무 오래 걸려서 플로이드 알고리즘으로 구현해보았다. 요지는, 자신보다 키가 큰 사람 + 자신보다 키가 작은사람이 n-1 명이면 자신의 키가 몇 번째 인지 정확히 알 수 있다.

결국, 자신보다 키가 큰 사람의 수와 자신보다 키가 작은 사람의 수를 구하는 문제인데, 이를 플로이드 알고리즘으로 구현하였다.

i학생이 j학생보다 키가 작고, 이를 그래프로 표현했을 때, i에서 j까지의 최단거리가 존재한다. 자신을 k번째 학생이라고 하면, 자신을 제외하고 i에서 k까지의 경로의 수가 곧 자신보다 키가 작은 사람의 수가 되고, k부터 i까지의 모든 경로의 수가 곧 자신보다 키가 큰 사람의 수가 된다.

자바로 문제를 해결하다보니 점점 익숙해지기 시작했다.

풀이 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n, m, a, b, res = 0, cnt;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        boolean ary[][] = new boolean[n][n];

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            ary[a - 1][b - 1] = true;
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n ;j++) {
                for(int k = 0; k < n; k++) {
                	if(ary[j][i] && ary[i][k])
                		ary[j][k] = true;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            cnt = 0;
            for(int j = 0; j < n; j++) {
            	if(i == j) continue;
                if(ary[i][j] || ary[j][i]) cnt++;
            }
            if(cnt == n - 1) res++;
        }

        System.out.println(res);
    }
}