[SWEA/D4] SWEA 5643 [Professional] 키 순서(Java)

문제 출처

SW Expert Academy

 

알고리즘 분류

• 최단 거리 알고리즘

 

풀이

dp[A][B]면 A보다 B가 키가 더 크다는 것이고, dp[B][A]면 A보다 B가 키가 더 작다는 뜻이다.

M가지의 키 정보를 기록하고 플로이드-워셜 알고리즘을 사용하여 N명 전체의 키의 상관관계를 기록한다.

i번째 행에서는 i번째 사람보다 키가 큰 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.

i번째 열에서는 i번째 사람보다 키가 작은 것이 확실하다면 1 이상의 숫자가 기록될 것이고, 그게 아니라면 -1일 것이다.

이를 이용해서 i번째 사람보다 키가 큰 사람과 키가 작은 사람의 수를 구할 수 있고, 이를 합산한 수치가 N - 1이라면 i번째 사람은 자신이 몇 번째로 키가 큰 지를 알 수 있게 되는 것이다.

 

코드

import java.io.*;
import java.util.*;

public class Solution {
	
	private static int N, M;
	private static int[][] dp = new int[501][501];
	private static int[] next = new int[501];
	private static int[] prev = new int[501];
	private static int Answer;
	private static StringBuilder sb = new StringBuilder();
	
	private static void init() {
		for (int i = 0; i < 501; i++) {
			next[i] = 0;
			prev[i] = 0; 
			for (int j = 0; j < 501; j++) {
				if (i == j) continue;
				dp[i][j] = (int) 1e9; 
			}
		}
		Answer = 0;
	}

	private static void settings() {
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					if (i == j) continue;
					dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]); 
				}
			}
		}
		
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j) continue;
				if (dp[i][j] != (int) 1e9) {
					next[i]++;
				}
				if (dp[j][i] != (int) 1e9) {
					prev[i]++;
				}
			}
		}
		
		for (int i = 1; i <= N; i++) {
			if (next[i] + prev[i] == (N - 1)) {
				Answer++;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("5643_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            init();
            
            sb.append("#" + test_case + " ");

            N = Integer.parseInt(br.readLine());
            M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
            	String[] inputs = br.readLine().split(" ");
            	int A = Integer.parseInt(inputs[0]);
            	int B = Integer.parseInt(inputs[1]);
            	dp[A][B] = 1;
            }
            
            settings();
            
            sb.append(Answer + "\n");
        }
         
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

}