오늘 풀어본 문제는
백준 2458번 키순서 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static boolean [][] students;
    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());

        students = new boolean[n+1][n+1];

        for(int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int fst = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());

            students[fst][sec] = true;
        }

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                for(int k = 1; k <= n; ++k)
                {
                    if(i == j || j == k || i == k) continue;
                    if(!students[j][k])
                    {
                        if(students[j][i] && students[i][k]) students[j][k] = true;
                    }
                }
            }
        }
        int answer = 0;
        loop : for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <=n; ++j)
            {
                if(i == j) continue;
                if(!(students[i][j] || students[j][i])) continue loop;
            }
            answer++;
        }
        System.out.print(answer);
    }
}

📝 풀이

우선 각 학생간의 연결관계만 확인된다면 누가 크고 작은것은 관련이 없기때문에

students 배열을 boolean타입으로 선언하였습니다.

플로이드와샬 알고리즘을 활용하여 직접적으로는 키를 비교할 수는 없지만, 다른 경로(학생)를 통해 비교될 수 있는 노드들의 여부를 확인하여 true로 변경해줍니다.

마지막으로, 모든 학생과 연결되어있는 각각의 학생을 찾아 answer값을 카운트 해줍니다.

📜 후기

어제 비슷한 느낌의 문제를 풀었는데, 자꾸 시간초과가 나길래!

다른분의 코드를 참고해봤더니 dp의 개념과 비슷하게 플로이드-와샬 알고리즘이

있더라구요. 모르는부분을 그냥 넘어갈 수 없기 때문에...

대놓고 플로이드와샬 알고리즘 문제를 골라보았습니다!