[백준] 2458 키 순서

2458번: 키 순서

 

boj.kr

풀이

[프로그래머스] 순위 와 동일한 문제이다. 플로이드 워셜 알고리즘을 사용해서 모든 학생들 간의 관계를 알아낸다. 그리고 본인을 제외한 모든 학생들과 관계가 있는 학생들을 세주면 된다.

코드

C++

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<vector<bool>> adj;

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    adj = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a][b] = true;
    }

    floyd_warshall();

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <= n; j++)
            if (adj[i][j] || adj[j][i]) count++;
        if (count == n - 1) answer++;
    }
    cout << answer << '\n';
    return 0;
}

Python3

import sys

input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
adj = [[False] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().rstrip().split())
    adj[a][b] = True


def floyd_warshall():
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if adj[i][k] and adj[k][j]:
                    adj[i][j] = True


floyd_warshall()

answer = 0
for i in range(1, n + 1):
    count = 0
    for j in range(1, n + 1):
        if adj[i][j] or adj[j][i]:
            count += 1
    if count == n - 1:
        answer += 1
print(answer)