문제) 백준 - 플로이드 와샬 - 역사
https://www.acmicpc.net/problem/1613
1613번: 역사
첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.
www.acmicpc.net
전/후 관계가 있는 역사 사건들이 주어질 때, 임의의 두 사건의 전/후 관계를 구하는 문제였습니다. 사건의 개수가 최대 400이므로 플루이드 와샬 알고리즘(O(N^3))으로 해결할 수 있습니다. >, < 관계를 1, -1로 저장하여 같은 전/후 관계끼리만 비교가 가능하므로 update 합니다.
C++ 소스코드)
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이 (0) | 2022.03.17 |
|---|---|
| [백준] 9935번 - 문자열 폭발 (C++) 문제 및 풀이 (0) | 2022.03.17 |
| [백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 (0) | 2022.03.16 |
| [백준] 1261번 - 알고스팟 (C++) 문제 및 풀이 (0) | 2022.03.14 |
| [백준] 20152번 - Game Addiction (C++) 문제 및 풀이 (0) | 2022.03.13 |
댓글