[백준] 2458: 교환 - JAVA

in Algorithm on 그래프 이론

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

풀이

1 ~ n번 학생들에 대해

m개의 관계가 주어지는데, 각각의 관계에는 a번 학생이 b번 학생보다 작다는 것을 알려준다.

이 관계들을 이용해 자신이 몇 번째 등수인지 정확히 알 수 있는 사람의 수를 세는 문제이다.

모든 정점끼리 탐색을 해야하기 때문에 플로이드-워셜 알고리즘을 사용했다.

플로이드-워셜은 O(n^3)의 시간복잡도를 갖는다.

핵심 로직은 다음과 같다.

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (list[i][k] && list[k][j]) {
                list[i][j] = true;
            }
        }
    }
}

i와 k가 연결되어있고, k와 j가 연결되어 있다면, i와 j는 연결되었다고 보는 것이다.

모든 정점끼리 연결 여부를 체크했다면 각 학생별로 연결된 학생의 수가 n-1인지 확인하면 된다.

메모리: 36932KB

시간: 604ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] list = new boolean[n][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a - 1][b - 1] = true;
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (list[i][k] && list[k][j]) {
                        list[i][j] = true;
                    }
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < n; i++) {
            int tmp = 0;
            for (int j = 0; j < n; j++) {
                if (list[i][j] || list[j][i]) {
                    tmp++;
                }
            }
            if (tmp == n - 1) {
                answer++;
            }
        }

        System.out.println(answer);
    }

}