[99클럽/파이썬 챌린저/6일차] 키 순서

백준 2458번 키 순서 G4

 

문제
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

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

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

 

 

그래프 이론, 그래프 탐색, dfs, 최단 경로, 플로이드 워셜

 

오늘은 플로이드 워셜 문제가 나왔다.

키 순서를 방향 간선으로 보고 이동 가능한 모든 경로를 탐색하였다.

학생 i에 대해 (dp [i][e] or dp [e][i])가 참이면, 키 순서를 알 수 있음을 이용하였다.

 

for문에 else를 사용하여 인원 체크를 사용하여 따로 개수 체크를 하지 않았다.

 

import sys

def solution():
    n, m = map(int, sys.stdin.readline().split())
    
    dp = [[False] * (n+1) for _ in range(n+1)]
    
    for _ in range(m):
        s, e = map(int, sys.stdin.readline().split())
        dp[s][e] = True
    
    for i in range(1, n+1):
        dp[i][i] = True
    
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if dp[i][k] and dp[k][j]: dp[i][j] = True
    
    result = 0
    for v in range(1, n+1):
        for e in range(1, n+1):
            if not (dp[v][e] or dp[e][v]): break
        else: result += 1
    
    print(result)
solution()

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

bool dp[501][501] = {false, };

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

    int n, m; cin>>n>>m;

    while (m--)
    {
        int s, e; cin>>s>>e;
        dp[s][e] = true;
    }

    for (int i = 1; i <= n; ++i)
        dp[i][i] = true;
        
    for (int k = 1; k <= n; ++k)
         for (int i = 1; i <= n; ++i)
             for (int j = 1; j <= n; ++j)
                 if (dp[i][k] && dp[k][j]) dp[i][j] = true;

    int result = 0;
    for (int i = 1; i <= n; ++i)
    {
        int cnt = 0;
         for (int j = 1; j <= n; ++j)
         {
             if (!dp[i][j] && !dp[j][i]) break;
             ++cnt;
         }
        if (cnt == n) ++result;
    }
        
    cout<<result;
}

---