08/28 키순서 BOJ 2458 파이썬

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

2458번: 키 순서

1. 풀이

전형적인 플루이드 마셜 구현 문제이다. 플루이드 마셜은 모든 노드에대한 모든 노드의 최단 거리를 구하는 알고리즘이다.

 

특정한 학생의 키순서를 알기 위해선 자신보다 몇 명이 큰지 그리고 몇명이 작은지 전체 학생 수에 대해서 알아야한다.

예를 들어 전체 학급 구성이 8명인 반에서 학생 A가 전체 반에서 4번째로 크다고 가정해보자.

이 학생이 4번째로 큰 학생임을 알기 위해선 위로 3명 아래로 4명이 있음을 알아야 본인이 4번째로 큰지 알 수 있다.

 

학생을 노드로 표현하고 대소관계를 간선으로 표현한 방향 그래프에서 학생 A보다 큰 학생수는 학생 A에서 도달할 수 있는 노드의 수와 동일하다.

즉 학생 A와 연결되어 있는 노드의 수를 세면 된다. 이를 위해서 인접 행렬을 통해 비교되어 있는 간선을 1로 표시하고

플루이드 마셜을 돌면서 A-> B , B-> C 와 같은 두개의 연결관계가 있으면  adj[A][C] 에 1을 표시해준다.

마지막으로 인접 행렬을 돌면서 대소관계가 있는 노드들에 대해 횟수를 더해주고 이 값이 전체 학생수 N보다 1이 작은 수이면 해당 노드는 자신이 학급에서 얼마나 큰지 알 수 있게 된다. 

N, M = map(int, input().split())
adj = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    p, c = map(int, input().split())
    adj[p-1][c-1] =1
for i in range(N):
    for row in range(N):
        for col in range(N):
            if adj[row][i] +adj[i][col]  ==2:
                adj[row][col] =1

cnt =[0 for i in range(N)]
for i in range(N):
    for j in range(N):
        if adj[i][j] ==1:
            cnt[i] +=1
            cnt[j] +=1

print(cnt.count(N-1))

 

2. 다른 풀이

개념은 동일하게 자신보다 큰 값과 작은 값을 세는 방식

DFS를 통해 시간 복잡도를 줄였다.

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m=map(int,input().split())

taller=[set() for _ in range(n)]
shorter=[set() for _ in range(n)]

e=[[] for _ in range(n)] #자기보다 큰 노드들이 적혀있는 인접리스트
e_inv=[[] for _ in range(n)] #자기보다 작은 노드들이 적혀있는 인접리스트

for _ in range(m):
  a,b=map(int,input().split()) #입력을 받으면서
  e[a-1].append(b-1) #큰 관계
  e_inv[b-1].append(a-1) #작은 관계 각각 입력
  
v=[0 for i in range(n)] # 큰 값 세기
v_inv=[0 for i in range(n)] # 작은 값 세기

def find_taller(i): #DFS로 자기보다 큰 관계 있는 학생수를 센다
  if v[i]: return taller[i]
  v[i]=1
  for j in e[i]: #인접리스트에서
    taller[i].add(j)
    taller[i]|=find_taller(j)
  return taller[i]
  
def find_shorter(i):#DFS로 자기보다 작은 관계 있는 학생수를 센다
  if v_inv[i]: return shorter[i]
  v_inv[i]=1
  
  for j in e_inv[i]:
    shorter[i].add(j)
    shorter[i]|=find_shorter(j)
    
  return shorter[i]
  
c=0
for i in range(n):
  find_taller(i)
  find_shorter(i)
  if len(taller[i])+len(shorter[i])==n-1: c+=1
print(c)