[Algorithm] 🐿️ 99클럽 코테 스터디 6일차 TIL : 백준 2458 키 순서

🔍문제

https://www.acmicpc.net/problem/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번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

🤔발상

자신의 키가 몇 번째인지 알 수 있는 학생이 누군지 고민을 했습니다.
문제에서 이미지로 주어진 그래프를 관찰하다보니, 한 학생이 다른 학생과 모든 학생과 직,간접적으로 연결 관계가 존재하면 자신의 키가 몇 번째 인지 알 수 있다고 보았고, 플로이드 워셜 알고리즘을 이용하여 연결 관계를 파악하고, 이 숫자를 세어 전체 인원수와 비교하면 될 것으로 보았습니다.

🔦입출력

다행이 학생 수가 500 이하로, 만약 10,000등 수가 많았으면 다른 그래프 탐색방법을 고민해보았어야 할 것 같은데 플로이드 워셜을 사용할 수 있을 것 같습니다.

📃의사코드

- 데이터 입력받기
- 플로이드 워셜 이용하여 연결관계 업데이트
- 각 학생의 연결된 인원 수 세기
- 모든 학생과 연결된 학생의 수 세기

👨‍💻코드

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

public class Main {
public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            HeightUtil heightUtil = new HeightUtil(n, m);
            heightUtil.init(br);
            bw.write(String.valueOf(heightUtil.getResult()));
        }
    }
}

class HeightUtil {

    boolean[][] graph;
    int[] dist;
    int n;
    int m;

    public HeightUtil(int n, int m) {
        this.n = n;
        this.m = m;
        graph = new boolean[n + 1][n + 1];
        dist = new int[n + 1];
    }

    public void setGraph(int a, int b) {
        graph[a][b] = true;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; ++k) {
            for (int j = 1; j <= n; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (graph[i][k] && graph[k][j]) {
                        graph[i][j] = true;
                    }
                }
            }
        }
    }

    public void setDist() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] || graph[j][i]) {
                    dist[i]++;
                }
            }
        }
    }

    public int getResult() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == n - 1) {
                result++;
            }
        }
        return result;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < m; i++) {
            String[] ab = br.readLine().split(" ");
            int a = Integer.parseInt(ab[0]);
            int b = Integer.parseInt(ab[1]);
            setGraph(a, b);
        }
        floydWarshall();
        setDist();
    }
}

🚀TIL

• 다른 탐색 방법도 한번 고민해보고 구현해보면 좋을 것 같습니다.