백준 14217 자바 - 그래프 탐색 (BOJ 14217 JAVA)

문제 : https://www.acmicpc.net/problem/14217

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14200/BOJ_14217.java

 

  문제 길이에 비해 사실 생각보다 쉬운 문제이다. 결국 시간복잡도가 문제인데, 가장 쉽게 생각할 수 있는 방법은 그냥 무작정 q줄에 대해 매번 해당 edge를 추가하거나 제거한 후 최단거리를 찾아보는 방식이다. 그럼 최단거리 찾기에 가장 간단한 bfs부터 보자. O(V+E) 정도이므로, O(N^2)정도고, q가 최대 500번이므로 최종적으로 최악의 경우 O(500^3) 정도로 별 문제가 없다는걸 알 수 있다.

 

  그러니 그냥 입력 쫙~ 받고 q줄에 대해 매번 간선을 제거하거나 추가한 후 bfs 돌리고 매번 최단거리 출력하면 된다. 추가로 간선 표현에 이 경우 인접 리스트가 성능이 좋겠으나, 일반적으로 사용하는대로 List로 처리하자니 삭제연산이 오래걸린다. (ArrayList일 경우에도 어차피 찾아가는데 O(N) 필요하다. 비교하면서 이동해야하니. 거기다가 삭제 후 배열 유지에 O(N), LinkedList의 경우 삭제 위치까지 찾아가는데 O(N)). 그래서 처음엔 HashSet 으로 처리해봤으나, 이 경우 삽입 삭제는 당연히 O(1)이나, key들 탐색이 좀 오래걸린다. 그래서 그냥 인접행렬로 해보니 오히려 이게 더 빨랐다. 코드는 그래서 인접 행렬로 처리한 코드이다.