[백준] 2458번 파이썬 _ 키 순서

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

2458번: 키 순서

문제유형 : 구현, 플로이드와샬

 

문제풀이 :

• 얼마전에 프로그래머스에서 푼 https://esoongan.tistory.com/178랑 아주 똑같은문제였다! 역시 한번이라도 푼 문제랑 비슷한 문제면 금방 푸는것같다. 양치기가 답인가?
• 문제 키포인트
  • 내 자식노드의 부모노드에 내 부모노드를 추가한다.
  • 내 부모노드의 자식노드에 내 자식노드를 추가한다.
• 약간 주의해야 할 점이 있는데 만약
  • 내 부모의 부모들을 내 부모로 가져오는식으로 코드를 짜면, 즉 내 자식의 자식들까지 내 자식으로 끌고오는 식으로 하면
  • 내 부모의 부모도 아직 모든것을 확인하기 전이기때문에 추후에 부모의 부모에게 더 많은 부모노드가 생길수 있다.
  • 그래서 위 방식대로 풀면 n번반복으로 끝나지않고 더 확인해줘야하는 상황이 발생한다.

 

그리고 이문제를 플로이드와샬로 풀수도 있는데 그러면 pypy3로 제출해야 시간초과가 안난다.

 

 

 

잘못된건 아니지만 이렇게하면 반복문을 더 돌아줘야함

# 내 부모의 부모는 내 부모다
# 내 자식의 자식은 내 자식이다.
# for i in range(1,n+1):
#     temp = set()
#     for p in parent[i]:
#         temp.update(parent[p])
#     parent[i].update(temp)
#     temp = set()
#     for c in child[i]:
#         temp.update(child[c])
#     child[i].update(temp)

정답코드 

import sys
input = sys.stdin.readline

# 학생들의 수와 비교횟수
n,m = map(int, input().split())

parent = [set() for _ in range(n+1)]
child = [set() for _ in range(n+1)]


for _ in range(m):
    a,b = map(int, input().split())
    # a가 b보다 키가 작다..
    # a의 부모에 b를 추가하고, b의 자식에 a를 추가한다.
    parent[a].add(b)
    child[b].add(a)


# 내 자식의 부모에게 내 부모를 준다.
# 내 부모의 자식에게 내 자식을 준다.
for i in range(1,n+1):
    for j in child[i]:
        parent[j].update(parent[i])
    for j in parent[i]:
        child[j].update(child[i])

cnt = 0
for i in range(1,n+1):
    if len(parent[i])+len(child[i])==n-1:
        cnt += 1

# 최종적으로 i노드의 부모노드수와 자식노드수가 n-1이면 정확히 알 수 있다.
print(cnt)