[백준] 8452. 그래프와 쿼리

https://www.acmicpc.net/problem/8452

접근법

• 간선을 붙이면서 출력을 처리해주면 되고 BFS를 수행하면 되는데
• 생각하는 방식의 시간복잡도 계산이 어려웠다.
• 시간 복잡도 계산을 생각해보자
  • 쿼리마다 bfs를 수행하면 $O(Q * (V+E))$ 임
  • 그런데 다른 해설들을 찾아보면 "각 노드가 갱신되는 횟수"를 기준으로 하고있음
  • 생각해보니 전체 bfs를 수행할 것은 아니고 일부만 bfs를 수행할 예정이었는데, 이런 경우의 시간 복잡도 계산이 달라진다!
  • 값의 "갱신"을 기준으로 보면 다르게 보인다는 이야기
  • 결국 크게 봤을때 각각 점들의 거리가 갱신이 될 테고, 갱신은 무한정으로 되진 않을테고..
  • 어렵다
    • 노드의 입장에서 보면 간선하나 추가되고 갱신되고, 하나 추가되고 갱신되고...를 최대 M번 반복한다는 이야기(그 이상은 불가능함)
    • 노드의 갱신 $O(NM)$ 이 시간 복잡도가 된다는 개념
• 이렇게도 생각해볼 수 있겠다
  • 노드가 가질수 있는 거리는 1 ~ 1000까지임
  • 즉 갱신은 최대 1000번 발생함
  • 갱신이 발생하면 주변 노드를 탐색할 것임(연결된 간선수만큼)
  • 모든 노드가 1, 2, ... 1000으로 갱신되었다고 보면
  • 갱신할때마다 $O(E)$만큼 탐색을 수행하니 $O(1000*E)$
  • 여기서 1000이라는 숫자는 노드의 숫자임(간선의 길이가 1이니까 멀어봐야 노드의 숫자만큼 멀다는 이야기)
  • 즉 $O(VE)$