[백준/2548/파이썬] 키 순서

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

2458번: 키 순서

Problem

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

조건

• 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다.
• 방향성을 가진 그래프로 나타낸다. 1<5 이면, 1->5의 관계로 나타낸다.
• a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.
• 첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다.
• 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

SOL

전형적인 그래프 문제이지만, 조건이 조금 생긴 문제이다.

한 노드를 기준으로 2가지 인접 그래프를 탐색해주면 해당 조건에 맞는 친구를 찾을 수 있는 문제이다.

대소관계를 그래프로 나타낸거이기 때문에, 한 노드에서 다른 노드로 모두 도달할 수 있으면, 그 노드는 대소관계가 명확해진다. 대신, 이 그래프는 단방향 그래프이므로, 자기보다 큰 친구들, 자기보다 작은 친구들 모두 탐색해봐야한다.

(즉, A>B 이면, A는 B보다 큰 의미도 맞지만, B는 A보다 작다도 맞는 말이기 때문)

• 주어진 방향 그래프
• reverse된 방향 그래프

이 2가지 인접 그래프를 돌면서, 한 노드에서 탐색했을 때, 모든 노드에 도달 할 수 있다면, 그 노드의 대소관계는 명확해진다.

#Graph문제
#adj List로 구현
import sys
sys.setrecursionlimit(10000)
V,E =map(int,input().split())
adj=[[] for _ in range(V)]
r_adj=[[] for _ in range(V)]
ans=0

for i in range(E):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    r_adj[b-1].append(a-1)

#DFS
def dfs(n):
    visited[n] = True
    for nxt in adj[n]:
        if not visited[nxt]:
            dfs(nxt)

def dfs2(n):
    visited[n] = True
    for nxt in r_adj[n]:
        if not visited[nxt]:
            dfs2(nxt)

for i in range(V):
    visited=[False]*V
    dfs(i)
    dfs2(i)
    #print(visited)
    if False in visited:
        continue
    else:
        ans+=1

print(ans)