백준 1613. 역사

tose33 2022. 9. 24. 12:33

1613번: 역사

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

www.acmicpc.net

이 문제는 처음에 위상정렬 (topology sort) 인것 같았지만 좀 보다보니 얼마전에 풀었던 floyd warshall을 이용한 문제와 거의 같은 문제 였다.

백준 10159. 저울

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의..

tose33.tistory.com

10159. 저울 문제랑 거의 똑같은 문제다.

다른점이라면 두 노드의 순서를 파악해야 하는 점인데 다음은 예제를 floyd warshall을 돌린 결과다

노드 1과 5의 관계를 생각해보자.

위 결과를 보면 [1][5] = flase 이고 [5][1] = false 이다.

즉 노드 1과 5는 서로 연결되지 않았음을 알수 있다.

노드 2와 4의 관계를 생각해보자.

[2][4] = true, [4][2] = false 이다.

따라서 노드 2 이후에 4가 나타난다는 것을 알 수 있다.

노드 3과 1의 관계를 생각해보자.

[3][1] = false, [1][3] = true 이다.

따라서 노드 1 이후 3이 나타난다.