[sw정글 3주차] 다익스트라 vs BFS 뭐가 더 빠르게~~?

Date: 2022.10.11 Updated: 2022.10.11

📚SW정글 3.8주차

(대전은 항상 날씨가 좋은 것 같다. 서울에만 있을 때는 이런소리하면 이해가 안되었겠지만..)

이번글 에서는 그래프에 대해 공부하면서 혼자 깨닫기 아까운 내용들에 대해 정리하였다. 그래프에 대한 전반적인 이해와 내용들은, 킹-갓 근본 알고리즘 원서 CLRS를 원서로 읽으며 정확하게 정리해 나갔다.

처음에는 아니 왜 이런 식으로 설명을 해두었지? 라고 생각하였지만, 글을 계속 읽어나가다 보니 무릎을 탁! 치게 된 순간들이 있었다.

✌️2wheeh

CLRS를 파다보니 물어볼 사람이 별로 없었다. u.d, v.f, s ~> v, G(V,E), white-gray-black, f(C) 등과 같은 표현들이 처음에는 많이 낯설었다. 그럼에도 불구하고, 나와 정글에 함께 온 과동기…이자 친구이자.. 이제 곧 커리어 동기가 될 이원희씨(링크)의 도움을 많이받을 수 있었다. 같이 CLRS에 대해 이야기할 수 있는 유일한 사람이라 더 큰 도움이 되었다.

dfs (이원희씨의 블로그: 한방에 이해되는 깔끔한 설명이다)

un-humanism (이원희씨의 블로그: 역시 확 와닿는 설명이다… ~~여기까지만 알아보도록 하겠다~~)

🚀이 글의 내용

이야기를 하던 중 다른 사람들에게 소개해도 좋을 것 같은 개념 몇가지를 가져와보았다. 이 글을 읽고나면…

☀️Gray node가 무엇인지
☀️다익스트라 vs BFS 뭐가 더 빠른지
☀️다익스트라의 시간복잡도
☀️크루스칼과 connected components의 유사성에 대해서
☀️프림과 다익스트라의 유사성에 대해
☀️최단거리 문제들, 위상정렬을 관통하는 개념

에 대해 알 수 있다.

📊그래프

gray node 개념에 대해 먼저 말해볼까 한다. 아직 발견하지 않은 node는 white, 이제 큐에 들어가서 어떤 자식들과 연결되어있는지 확인하는 중에 있는 노드는 gray-node, 이미 발견을 완료한 node는 black 이다. 보통은 검사한’놈과 검사안’한놈 알고있지만, gray-node를 알고있으면 편하다.

내가 현재 작업중인 node에 대한 개념을 가져갈 수 있기 때문이다. 이 개념이 바로 frontier에 대한 것이다. 예를들어, 백준18352번와 같은 경우 BFS를 활용하는 문제이다. BFS의 핵심 개념이 무엇인가?

BFS의 핵심 개념은, 어느 한 vertex를 중심으로 동일한 거리를 형성하는 frontier를 골라낼 수 있는 것이다.

이때, frontier는 gray-color 이라고 표현하고, 다른 그래프 개념들을 이해할 수 있도록 도와준다. 단순 개념 이해뿐만이 아니라, 코드에서도 적용되어야 한다.위의 백준18352번을 풀기위한 코드의 일부이다. 거리가 K인 도시를 찾기 위해 아래와 같은 알고리즘을 사용하였다.

while queue:
    dist, u = heapq.heappop(queue)
    
    if costs[u] == K:
        ans.append(str(u))
        continue

하지만 이렇게 될 경우 문제가 생긴다. frontier끼리 인접해 있는 경우, queue에 들어있는 녀석들은 if문을 통해 검사당하는 시점에서 이미 k+1로 갱신되고 있기 때문이다. k보다만 크면 안간곳이겠지? 라고 생각하면 반례가 생긴다.

while queue:
    dist, u = heapq.heappop(queue)
    
    if costs[u] > K+1:
        ans.append(str(u))
        continue

frontier끼리 인접해 있어서, if k>1과같이 조건을 걸게 된다면, k+1이니까 안갔다고 판단해버려서 거리를 k+2로 저장해버리기 떄문이다. 따라서 검사당하고있는.. gray area개념을 가져가게 된다면, 이와같은 실수를 막을 수 있다. 그리고 gray area를 기준으로 이미 BFS가 휩쓸고 지나간곳은 black! 아직 개척 해 나가야 할 영역은 white! 로 정의하면 BFS가 한눈에 쏙 들어올 것이다. 다시한번 말하자면 frontier를 기준으로 쫙! 나누어 버릴수 있는게 BFS의 핵심인 것이다 frontier끼리 인접해 있어서, if k>1과같이 조건을 걸게 된다면, k+1이니까 안갔다고 판단해버려서 거리를 k+2로 저장해버리기 떄문이다. 따라서 검사당하고있는.. gray area개념을 가져가게 된다면, 이와같은 실수를 막을 수 있다. 그리고 gray area를 기준으로 이미 BFS가 휩쓸고 지나간곳은 black! 아직 개척 해 나가야 할 영역은 white! 로 정의하면 BFS가 한눈에 쏙 들어올 것이다. 다시한번 말하자면 frontier를 기준으로 쫙! 나누어 버릴수 있는게 BFS의 핵심인 것이다

백준11725번문제의 경우, 부모의 노드를 표시해 주는 문제이다. 부모의 노드를 어떻게 표시 해 줄까? gray가 새로운 white를 탐색하는 동안 white들에게 "gray가 너네 엄마(부모)란다" 라고 표시해주면 된다. 이처럼 gray-color(frontier)개념을 알고 있으면 쉽게 풀 수 있는 문제들인 것이다.

☕️small tip about DFS

참고로 DFS가 재귀로 이루어진 집합임을 이해하는 가장 핵심 개념은 white-path Theorem이다. 이도 white-color 개념을 이용해서 설명해 주는데, (u,v) edge에 대하여 모두 white vertice면 v는 u의 자손이라는 것이다. 이처럼 각 개념들의 핵심을 설명할 때, color개념들이 인용되곤 한다.

🚀BFS와 다익스트라에 대하여

BFS의 시간복잡도를 알고있는가? BFS의 시간복잡도는… 바로바로… ممسجددج이다! 오잉?🧐

일단 그래프들의 시간복잡도에 대해 자세히 알아보도록 하겠다. BFS의 시간복잡도는 인접행렬로 구현할 경우…

while queue:
  for V:
    연결된 행렬 검사

위처럼 한 노드를 확인하는데에는 O(V)가 걸리지만, 인접리스트는 한노드에 연결된 모든 노드를 확인하는데에 O(E)가 걸리므로.. 인접행렬은 O(V²)이 걸리고, 인접리스트는 O(V+E)가 걸리는 것이다.

E « V² 일 때는 인접리스트로, 그 이외의 경우에는 인접행렬로 처리하면 된다.

바꾸어 말하면, Sparse한 그래프는 인접리스트로, Dense한 그래프는 인접행렬로 처리하는게 좋다는 뜻이다.

🤔그렇다면 무조건 인접리스트?

그렇다면 대부분의 경우에 인접리스트를 쓴다. 그렇다면 인접행렬은 필요가 없을까? 당연히도 아니다. 백준의 미로문제유형들의 경우 인접행렬로밖에 표현할 수 없다. 하지만 이와같은 문제는 그래프라기보다는, 지도를 그린것이기 때문에 행렬로 표현했다고 하는게 더 정확할 것이다. 그렇다면 인접행렬은 정녕 필요없는 존재일까?

일단 메모리에 관하여 할 이야기들이 있을 것이다. Vertex의 크기가 비약적으로 커지게 된다면, 연결시켜둔 그래프의 크기도 따라서 커질 것이다. 인접행렬은 무방향 그래프에 대해, symmetric(좌우대칭)인 성질이 있으므로, 이를 이용하여 크기를 절반으로 줄일 수 있을 것이다. 또한, weight이 없는 그래프라면 그래프의 연결 여부를 단순 1과0의 1비트 표현으로 바꿀 수 있을 것이다. 메모리의 저장순서가 자동으로 index가 되므로 여기서 엄청난 메모리 절약을 불러올 수 있는 것이다.

(☕️small tip) 참고로 boolen 표현(True, False)값은 int와 거의 비슷한 크기를 가진다.

이어서 그래프의 표현에 대해 이야기하고 마무리짓겠다.

백준11724문제의 경우에도, 다음과 같은 조건이 주어진다.

boj adjacent list

보는바와같이 edge의 개수가, vertex의 제곱보다 훨씬 작다는 조건을 주고있다. 이는 우리에게 “인접리스트로 푸는게 훨씬 좋을거야~~” 라고 말해주는 것이다.

🚀그렇다면 BFS와 다익스트라는?

그렇다. 모든 노드에 대해 이중for문을 돌리던 BFS, 하지만 heap + continue를 사용해나가며 불필요한 경우를 쭉쭉 넘겨나갈 수 있다.

따라서 BFS( O(V²) ) => 다익스트라( O(ElogV) )로 확 줄어들 수 있다.

따라서 edge의 개수에 대해 dependency가 더 크다는 것을 생각 해 볼 수 있다. 하지만 이원희씨의 실험결과, V와 E의 개수가 크지 않은 상황에서는, 2차원으로 표현해둔 그래프를 dict + set으로 표현함 으로써 얻을 수 있는 이득이 훨씬훨씬 크다고 한다.

2차원배열에서 difaultdict를 사용함으로써 키값을 찾는 수고를 O(n) -> O(1)로 줄일 수 있고, set을 사용함으로써 value를 찾는 수고를 O(n) -> O(1)로 줄일 수 있는 것이다. 100개의 vertex가 100개의 연결을 가지고, for문을 돈다면…

100X100X100 => 100X1X1 즉, 이론상으로는 10000배 더 빠르게 검색할 수 있는것이다. 물론 locality의 영향을 받겠지만, 무튼 아주 많은 이득을 가져갈 수 있고, b반이원희씨의 실험결과에서도 확인할 수 있었던 것이다.

코딩테스트 관점으로 본다면, 코테 특성상 중복 그래프를 다량으로 넣어둔 케이스가 있지 않으까 싶은데 이를 set자료구조로 걸러내줄 수 있기 때문에 더욱 빛을 발하지 않을까 라고 생각한다.

❗️결론

따라서, BFS가 아닌 다익스트라의 heap + continue구조를 통해 시간절약을 했을지언정, 그래프를 그릴 떄 dict+set으로 해주지 않는다면 큰 시간이득을 기대하기 힘들다는 것이다.

👩‍❤️‍👩알고리즘간의 유사성에 관하여

여기서 설명할 내용은, 저번글에서 설명한 단하나의 중요한 내용(링크)을 알고 읽는게 좋을 것 같다. 위글에서 설명하듯, (S, V-S)로 나누었을 때, greedy하게 선택하면 그게 바로 최적의 해를 보장한다는 결론을 얻을 수 있었다.

다익스트라는 프림알고리즘과 비슷하다. 하나의 노드를 중심으로, 점점 한방에 한놈씩 확실하게 잡아가는 것이다. 그렇기 때문에, 다익스트라와 프림 알고리즘 모두 O(ElogV)의 시간복잡도가 걸리는 것이다. 그렇기에, 마찬가지로 다익스트라도 피보나치힙으로 구현할 시 O( VlogV + E )의 속도로 개선된다. black-color과, white-color area를 cut 하고나서, 이 때 선택할 수 있는 light edge를 선택하는 방식인 것이다. 따라서 MST에서 알게된 그 내용을 바탕으로 다익스트라에서도 똑같이 적용되는 것이다.

크루스칼은 connected component 알고리즘과 유사성을 지니고 있다. disjoint-set(서로소집합)인지를 확인하는 작업의 연속인 것이다. 크루스칼을 공부하면 필수적으로 나오는 union-find 알고리즘이 connected component를 검사하는 방법 중 하나인 것이다.

🚀위상정렬

위상정렬을 공부하다보면 SCC를 마주치게 된다. 친한친구들끼리 그룹핑 시켜주는 것이다. 위상정렬은 다음과 같은 로직을 따른다.

1. 각각의 vertex에 대해 종료시간 vertex_finish를 계산하기 위해 DFS(G)를 호출한다.
2. 각 vertex가 종료될 때마다 연결리스트들의 맨 앞에 삽입한다.
3. return 정점의 연결리스트

DFS는 O(V+E)의 시간복잡도를 가지고 있으며, 위의 기본로직2에서 vertex를 삽입하는데 걸리는 시간은 O(1)이므로, 위상정렬도 마찬가지로 O(V+E) 의 시간으로 해결할 수 있는 것이다.

😶‍🌫️SCC

필자가 가장 열심히 공부를 하고 증명해봤던 부분이다. SCC를 열심히 공부하였으나 이번주의 범위가 아니여서 아쉽다😂

개인적으로, 그래프를 공부해 나가며, 몇몇 개념들을 깨우치고 위상정렬을 공부 한 이후, SCC를 공부하며 무릎을 탁! 치게 되었다.(코사라주? 타잔? 이거 구현하다가 머리가 아팠던…) 다음주 알고리즘공부 범위에 SCC가 나온다면 정말 자세히 설명해 보도록 하겠다.(개인적으로는 MST와 SCC공부가 제일 재미있었으며, 문제풀이는 다익스트라가 가장 재미있었다)

🚀정리

그래프를 여러가지 방법으로 표현할 수 있다. 인접행렬은 V²이였으며, 인접리스트는 V+E였다. E가 엄청나게 큰 dense graph가 아니라면, 대부분의 경우 인접리스트를 사용하면 되며 그 판단기준은 E « V² 이 되는 것이다. 이원희씨의 실험으로 또한 많은것을 얻을 수 있었다. (DFS와 BFS 모두 V+E의 시간복잡도를 가지도록 구현되었을 때) 왜 다익스트라를 사용하면 빠를까? 에 대한 질문은 당연하게도 heap + continue를 활용하여 빠르게 넘어가는 부분이였다. 하지만 더욱 시간을 줄여줄 수 있는 부분은 2차원배열을 dict으로 한번, set으로 한번 더 줄여주는 것이다. 따라서 defalut(set) 구조를 사용함으로써 거대한 vertex집합에 대하여, n²의 검색 연산을 1로 줄여주는 엄청난 이득을 챙길 수 있었던 것이다.

아울러 MST에서 새로운 edge를 그어넣을 때, greedy한선택이 최선의 선택을 보장함을 알게되었다. 이처럼 weight가 고려되는 문제에서는 모두 이 개념이 사용된다. 이 개념이 프림과 다익스트라를 만들게 되었고, 또한 크루스칼과 connected-component 알고리즘에서 서로소 여부를 체크하며 계속 선택을 나아갈 수 있게 해주는 것이다.

gray컬러에 대해서도 언급하였다. 이는 현재 검사중인vertex들, frontier에 대한 개념을 알게 해 주고, 이 개념은는 BFS를 쉽게 이해하도록 도와준다. frontier를 기준으로 두 그룹으로 가를 수 있기 때문이다. 아울러 DFS의 근간이 되는 white-path theorem등 핵심적인 개념들을 이해할 때에도 이 색깔개념이 들어간다.

이러한 개념들은 SCC에서 다시한번 통합된다. 예를 들면, SCC로 나뉘어진 vertices에 대해, (u,v)간선이 C와 C’을 잇는다면, f(C) > f(C’)임을 증명하는 내용이 있다. 이럴 때에도, color개념을 통해 손쉽게 어려운 개념을 이해할 수 있다.

😵배우면서 깨달은 내용을 정리해 보았습니다. 틀린 것 같은 개념을 아래 댓글에 달아주시면 감사합니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

Sunny Yoon