백준 2458 키 순서 풀이 (feat. JAVA)

DFS를 양방향으로 해야하나? 라고 생각했던 문제

근데 그냥 플루이드 워셜을 쓰면 된다

플루이드 워셜이 전혀 몰랐던 경로 탐색 응애인 나는... 신세계를 발견해버리고 만다

이런게 있다고...? ㅋㅋㅋ 진짜 사람들은 천재인가보다;;

원리는 이해했고, 이론은 (비교적) 쉬운 편이라고 생각하는데 내가 또 구현해보라고 하면 그건 또 다른 얘기라

당분간은 최단 경로, 플루이드 워셜, 다익스트라 쪽을 공부해야할 것 같다

 

package Record;

/*
[백준]
2458, 키 순서

[문제파악]
- 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다.
- 단, N명의 학생들의 키는 모두 다르다고 가정한다.
- 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.
    1번 학생의 키 < 5번 학생의 키
    3번 학생의 키 < 4번 학생의 키
    5번 학생의 키 < 4번 학생의 키
    4번 학생의 키 < 2번 학생의 키
    4번 학생의 키 < 6번 학생의 키
    5번 학생의 키 < 2번 학생의 키

- 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다.
- a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.
- 1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다.
- 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다.
- 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다.
- 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.
- 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

[입력]
- 첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.
- 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 N보다 작거나 같은 서로 다른 양의 정수 a와 b가 주어진다.
- 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.

[출력]
- 자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.

[구현방법]
- 한 점에서 다른 모든 점들과 연결되어 있는지를 확인하면 될 것 같은데
- 정확히는 한 점으로 오거나 나가는 모든 방향을 체크해서 '한 점'에서 다른 모든 점들과 연결되는지를 확인해야할듯하다
- 그러니까 두가지 DFS가 있으면 될듯
    - 하나는 현재의 한 점으로 향하는 모든 점 (? -> 한개의 점 방향)
    - 다른 하나는 현재의 점에서 갈 수 있는 모든 점 (한개의 점 -> ? 방향)
- 구현하려고 보니 가장 큰 문제점이 있다. 현재 아이디어는 비효율의 극치임
    - 두가지 방향의 DFS로 한다고 한들 진입하는 노드를 찾기 위해선 모든 노드들을 찾아봐야하는게 비효율적이다
    - 예를들어 5로 진입하는 노드들을 찾으려면 1부터 N까지 5로 진입하는 것이 true인 노드를 찾아야한다
    - 1이 5로 진입한다고 가정하면 또 1부터 N까지 1로 진입하는 노드가 없는지 찾아야함
    - 1초 내에 못풀고 터질 위험도 있다 N은 500까지 주어지는데, 이걸 한 노드로 연결되는 애들을 찾을 때마다 N번 반복하는 것? 불가능
        - 더군다나 한 노드에 여러개가 연결되어 있으면? 그러면 찾기도 전에 터져버릴게 분명하다
- 구현 방법 고민하는데 20분 초과하여 확인해보니 플루이드 워셜을 써야한단다... (그게 먼뎅...)
- 플루이드 워셜을 전혀 모르기 때문에 이 문제는 공부하는 방식으로 진행
- 아 추가로 정방향, 역방향을 저장하는 인접 행렬 두가지 버전을 만들어서 탐색하면 내가 고민했던 양방향 DFS의 소요 시간은 대폭 줄일 수 있을 것 같다
- 다만 알고리즘은 효율을 위해 존재하는 것인데 플루이드 워셜을 공부하기 싫단 이유로 그렇게 풀어버리면 말이 안되기에 공부하자

< 플루이드 워셜 >
- 시간 복잡도 O(n^3)이라, 그래프 크기가 작아 세제곱 해도 문제가 풀릴 때만 써먹을 수 있다
- 모든 노드간의 최단경로를 구한다 (다만 현 문제에서는 각 경로의 가중치가 없으니 연결된 것만 확인한다)
- 모든 노드들을 순차적으로 돌아가며 중간 노드를 잡고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다
- 즉 1 과 5가 연결되어 있어 1은 2를 못가는 상황이더라도 1이 5를 통해 2로 가는 경우 갈 수 있다고 판단한다
    - 이떄 가중치 경로의 경우 1 -> 5 -> 2 로 이동하는 두번의 가중치를 1 -> 2 에 기록한다
- 이걸 이 문제에 적용하면, 중간노드를 1 ~ N까지 잡고, 3중 for문을 돌린다
- 그럼 순차적으로 1부터 N까지 중간 노드 역할을 한번씩 하게 되고, 시작 노드와 중간 노드, 중간 노드와 종점 노드가 연결되어 있는 경우를 찾는다
- 찾게되면 이는 즉 시작 노드부터 종점 노드까지 (중간 노드를 거쳐) 연결되었다는 의미이다
- 그럼 이제 서로 연결된 노드들은 전부 연결 처리했으니 마지막에 이중 for문을 돌면서 isConnect[i][j] 또는 isConnect[j][i]가 연결된 것이 있는지 확이한다
- 둘 중 하나라도 연결되어 있다면 이는 곧, 서로 연결되어 있음을 의미하니 Count++을 해준다

[보완점]
- 이렇게 간단하게 풀린다니 어이가 없네...

*/


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

public class BOJ_2458_키순서 {
    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[][] graph = new boolean[N + 1][N + 1];

        // 입력으로 주어진 키 비교 관계를 저장
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph[a][b] = true;  // a -> b 방향으로만 연결
        }

        // 플로이드-워셜 알고리즘 (3중 for문 (= O(N^3))
        for (int mid = 1; mid <= N; mid++) {  // 중간 노드
            for (int start = 1; start <= N; start++) {  // 시작 노드
                for (int end = 1; end <= N; end++) {  // 끝 노드
                    // start에서 mid로 가는 경로가 있고, mid에서 end로 가는 경로가 있는지 확인
                    // 있다면, mid를 통해 start -> last는 연결되어 있다는 의미이다
                    // 다만 단방향이니 graph[start][end]만 연결되어있다고 표기
                    // 만약 가중치가 있는 경로였다면 이때 true가 아닌 (start -> mid 가중치) + (mid -> end 가중치)를 더해 기록하면 된다
                    if (graph[start][mid] && graph[mid][end]) graph[start][end] = true;
                }
            }
        }

        int result = 0;

        // 키 순위를 정확히 알 수 있는 학생 수 계산
        // 이제 인접 배열을 이중 for문으로 돌면서 start -> end 또는 end -> start가 연결된 것이 있는지 체크한다
        // 둘중 하나라도 되어있다면 count하고 최종적으로 (자기 자신을 뺀) N-1만큼의 갯수가 있다면 연결되어 있는 것으로 간주한다
        for (int i = 1; i <= N; i++) {
            int count = 0;

            for (int j = 1; j <= N; j++) {
                if (graph[i][j] || graph[j][i]) count++;
            }

            // 자기 자신 제외하고 모든 노드와 연결되어 있다면 +1
            if (count == N - 1) result++;
        }

        System.out.println(result);
    }
}