문제) 백준 - 플루이드 와샬 - 저울
https://www.acmicpc.net/problem/10159
10159번: 저울
첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩
www.acmicpc.net
N이 최대 100이므로 플루이드 와샬(O(N^3))로 충분히 해결할 수 있습니다. 대소 관계가 중요하므로 그 관계에 따라 1 또는 -1로 표현합니다. 만약 같은 t, i, j에 대하여 (i, t)와 (t, j)의 관계가 같으면 (i, j)의 관계로 표현합니다.
C++ 소스코드)
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 14620번 - 꽃길 (C++) 문제 및 풀이 (0) | 2022.03.13 |
|---|---|
| [백준] 11568번 - 민균이의 계략 (C++) 문제 및 풀이 (0) | 2022.03.11 |
| [백준] 21920번 - 서로소 평균 (C++) 문제 및 풀이 (0) | 2022.03.11 |
| [백준] 13164번 - 행복 유치원 (C++) 문제 및 풀이 (0) | 2022.03.11 |
| [백준] 14863번 - 서울에서 경산까지 (C++) 문제 및 풀이 (0) | 2022.03.08 |
댓글