백준 10159. 저울

tose33 2022. 9. 20. 13:59

10159번: 저울

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩

www.acmicpc.net

floyd warshall 을 이용하는 문제.

플로이드 워셜은 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘이다.

다르게 말하면 모든 정점들이 서로 이어져 있는지 아닌지 판단할수도 있다는 의미다.

플로이드 워셜을 돌리는데 거리는 필요없고 이어져 있는지만 알고 싶기 때문에 bool 형 배열로 만들어서

시작 정점 i, 거쳐가는 정점 k, 도착 정점 j라고 하면

d[i][j] = d[i][k] + d[k][j] 가 아닌

if(d[i][k] && d[k][j]) d[i][j] = true

이런 식으로 하면 i->k 경로가 존재하고, k->j 경로가 존재하면 i->j 경로가 존재한다는 것.