백준 2458 키 순서
키 순서
문제는 백준에서 확인 할 수 있다.
✔ 접근방법
- 자신의 키 순서를 정확하게 알기 위해서는 아래의 조건을 만족해야 한다.
조건 : 자신을 제외한 모든 노드와의 연관관계가 있어야 한다. - 플로이드워셜 알고리즘을 이용
- 자신을 제외한 모든 노드와의 연관관계를 확인한다.
- 조건에 맞는 노드의 수를 세어준다.
✔ 코드
import sys
if __name__ == "__main__":
answer = 0
N, M = map(int, input().split())
adj = [[0]*N for _ in range(N)]
for i in range(N):
adj[i][i] = 0
for _ in range(M):
a, b = map(int, sys.stdin.readline().rstrip().split())
adj[a-1][b-1] = 1
# for line in adj:
# print(line)
for mid in range(N):
for i in range(N):
for j in range(N):
# adj[i][j] = min([adj[i][j], adj[i][mid]+adj[mid][j]])
if adj[i][mid] == 1 and adj[mid][j] == 1:
adj[i][j] = 1
# for line in adj:
# print(line)
for i in range(N):
flag = True
for j in range(N):
if i != j and \
adj[i][j] == 0 and \
adj[j][i] == 0:
flag = False
if flag:
answer += 1
print(answer)
☝ 팁
- 백준 내의 python3 컴파일러로 답안을 제출하면 시간초과가 발생한다.
pypy 컴파일러로 답안을 제출하면 해결된다. - 플로이드-워셜의 최소가중치를 구하는 문제에서는, 일반적으로 3중 for문 안에 min()함수를 사용한다. 하지만 이 문제에서는 연관관계만 알면 되기에, 이에 맞게 체크만 해준다.
- min() 연산으로 인해 수행시간이 늘어나서 시간초과가 발생하게 되는 경우가 생기는데, 이를 방지해준다.
Author And Source
이 문제에 관하여(백준 2458 키 순서), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@aszxvcb/백준-2458-키-순서저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)