백준 1613, 1956 Java

문제

https://www.acmicpc.net/problem/1613
https://www.acmicpc.net/problem/1956

알고리즘 설명

둘 다 플로이드워셜 살짝 응용한 문제이다.
따로 글 쓰기에는 난이도가 있는 문제가 아니라서 2개를 합쳐서 썼다.

1. 역사
   사건A가 사건B보다 먼저 일어났으면 dp[][] 에 -1, 늦게 일어났다면 1, 모르면 0
   기본적인 플로이드 워셜 공식은 동일하지만
   dp[i][j] = dp[i][k]+dp[k][j] 에서 i~k 나 k~j 순서를 모른다면(0 이라면)
   update를 하면 안된다는 것만 주의하면 된다.
   사건A,B,C 의 순서가 엉키는 경우는 없으니 ik와 kj 값은 둘 다 동일하다.

2. 운동
   처음 봤을때는 플로이드워셜 이라고 생각을 못했다.
   DFS로 풀어도 될 것 같긴한데 플로이드워셜이 훨씬 간단하다.
   dp[i][j] 와 dp[j][i] 가 둘 다 값이 있다면 사이클이 생긴것이기 때문이다.
   (i--> j, j-->i 의 직접 경로가 없어도 K 를 거치는 경우까지 다 계산하기 때문에)
   이렇게 응용할 수도 있다는 것을 기억해두자..!

구현코드

https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B1613.java
https://github.com/melong222/SW/blob/master/SW/src/BACKJOON/B1956.java