[n2458] 키순서 in python

https://www.acmicpc.net/problem/2458

2458번: 키 순서

---

(처음 든 생각)

그래프를 사용해야하는 것 같긴한데..

방향그래프..

 

서로 연결되어 있는 부분을 이용해야할 것 같다..?

 

자신에게 오는 화살표는 자신보다 키가 작은 애들한테서 오는 화살표

자신에게서 나가는 화살표는 자신보다 키가 큰 애들에게 나가는 화살표

 

이 화살표의 개수가 총 n-1이면, 

해당 노드의 키순서는 알 수 있다.

 

그래서 answer+=1을 해주면 된다.

 

dp를 이용해야하는 건가?

dp가 가장 먼저 떠오르긴 했다.

 

dp를 이용해서 연결되어 있는 노드들의 정보를 저장해주는 것으로

방향을 잡았다.

 

 (이 문제 dp로도 구할 수 있는가 -> 질문 )

:: 플로이드 와샬 알고리즘은 다이나믹 프로그래밍 유형에 속한다

---

(풀이 : 플로이드와샬 (dp) )

 

i->k(경유)->j, 경유지를 중심으로 i와 j가 연결되어 있으면,

dp[i][j]를 1로 업뎃해준다.

 

연결되어 있는 정보들을 dp에 담아내는 것이기 때문에

 

 

맨 초기에 받아온 그래프의 값은, 모든 정점의 연결상태가 표현되어 있지 않다.

그냥 해당 정점에서 나가는 화살표만 명시되어있다.

따라서 우리는 모든 정점의 연결상태를 알아야하기 때문에

위와 같이 플로이드 워셜 알고리즘을 활용하여

모든 정점의 연결 상태를 구한다.

 

 

이제 해당 노드에 연결되어있는 노드의 개수가 n-1이면,

해당 노드의 키순서를 알 수 있다.

 

 

해당 노드가 0이라고 치면,

0에 연결되어 있는 노드의 개수는 총 4개 

n-1=5개가 되어야 키의 순서를 알 수 있는데

4개 이므로 0은 키순서를 알 수 없다.

(4,3,1,5)

---

해당 노드가 3일 경우

3에 연결되어 있는 노드의 개수는 총 5개

n-1=5개와 동일하므로

3의 키 순서는 알 수 있다.

---

'''
bfs - 한 정점으로부터 모든 정점으로의 최단거리
플로이드와샬 - 모든 정점 사이의 최단거리
'''
import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
array = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    array[a - 1][b - 1] = 1

# i->k->j : i와 j가 연결되어 있는지 확인하는 과정
# k는 경유지, i는 출발지, j는 도착지
for k in range(n):
    for i in range(n):
        for j in range(n):
            if array[i][k] == 1 and array[k][j] == 1:
                array[i][j] = 1

print(array)

answer = 0
for i in range(n):
    check = 0
    for j in range(n):
        check += array[i][j] + array[j][i]
    if check == n - 1:
        answer += 1
print(answer)