Ray`s Tech Lab

신장 트리 (Spanning Tree) ? 

하나의 그래프가 있을 때 그 그래프의 모든 노드를 가지고 있으면서 사이클(Cycle)이 없는 부분 그래프(Sub graph)!

원래 그래프가 N개의 노드를 가진다면, 그 놈의 신장트리는 N개의 노드와 N-1개의 간선(edge)를 갖는다. (간선이 N - 1개보다 적으면 모든 노드가 연결돼있지 않고 N - 1개보다 많으면 사이클이 있는 그래프다).

최소 신장 트리?

신장 트리는 원본 그래프의 부분 그래프이므로 당연히 여러 개 존재할 수 있는데, 그 중 간선들의 가중치 합이 가장 적은 신장 트리를 최소 신장 트리(MST, Minimun Spanning Tree)라고 부른다.

크루스칼 알고리즘?

주어진 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 그리디 알고리즘의 일종으로, 이해하기 매우 쉬운 알고리즘이다. 

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 선택되지 않은 간선 중 가장 가중치를 갖는 간선을 선택한다
3. 그 간선이 기존에 선택했던 간선들과 사이클을 이루지 않는지 체크. 만약 사이클을 이룬다면 그 간선은 버린다.
4. 모든 노드들이 골라질 때까지 2 ~ 3을 반복

모든 노드들이 골라지는지의 여부는 노드들을 세도 되고, 선택된 간선의 개수가 N - 1개인지로 해도 되고, 아니면 그냥 모든 간선들에 대한 조회가 끝날 때까지 해도 된다. 매 페이즈마다 사이클을 이루지 않게끔 골라왔으니 이렇게 만들어진 서브트리는 신장 트리임이 보장되며, 또한 매 페이즈마다 항상 작은 가중치를 갖는 간선들을 골라왔으니 이렇게 만들어진 신장트리는 당연히 최소 신장 트리임이 보장된다.

가장 까다로운 작업은 사이클을 이루는지 판단하는 작업인데, 이는 유니온 파인드를 통해서 간단히 판별할 수 있다.

※ 유니온 파인드에 대해 정리했던 글

https://jofestudio.tistory.com/11

유니온 파인드로 사이클을 판별가능한 이유

유니온 파인드를 이용하면 무방향 그래프에서의 사이클 판별이 가능하다. 방향 그래프에서는 DFS를 통해 가능함. 근데 어떻게 가능한 걸까?

우선 다음 작업으로 사이클을 판단가능하다.

1. 간선을 고른다.
2. 그 간선들에 딸린(?) 노드 두 개가 있을 것이다. 그 두 놈이 같은 집합에 있는지, 즉 같은 그래프에 있는지 확인한다.
3. 두 놈이 다른 그래프에 있다면 두 노드에 대해 Union연산을 한다. 두 놈이 같은 그래프에 있다면 사이클이 있는 거다.

왜 이 작업으로 사이클 판단이 된다는걸까?

유니온 파인드는 집합에 대한 연산들로 생각할 수 있다. 유니온은 두 집합을 합치는거고, 파인드(흔히들 getParant라는 이름으로 메서드를 짓기도 함)는 특정 원소가 속한 집합을 알려주는 연산인 거다. 여기서, 그래프를 일종의 집합으로 볼 수 있다!

이 그래프에서 가장 작은 노드를 리더로 생각한다면 어떨까. 그럼 위 그래프에서의 리더는 0이다. 

1이 속한 그래프의 리더 = 0 이다.

5가 속한 그래프의 리더 = 0 이다.

이런 식으로, 그래프를 하나의 집합으로 표현가능한 것이다. 

이 그래프에서, 우선 처음에 다음과 같이 리더 테이블을 만들어줬다고 하자. 육안으로 세 놈이 같은 그래프에 있는 걸 당연히 확인가능하지만 일단 각자가 서로 다른 그래프에 있다고 생각하고 테이블을 초기화한다.

간선 (1, 2)를 골랐다. 두 노드가 같은 집합에 속하는지(즉 두 놈이 속한 집합의 리더가 같은지)를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 2는 같은 집합, 즉 같은 그래프에 있다고 생각할 수 있다.

이번엔 간선 (1, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까, 다르다. 그럼 두 놈을 Union해준다.

즉 이제 노드 1과 노드 3은 같은 집합 즉 같은 그래프에 있다고 생각할 수 있는 거다.

이제 간선 (2, 3)을 골랐다. 두 노드가 같은 집합에 속하는지를 보니까 같은 집합에 있다! 노드 2가 속한 집합의 리더와 노드 3이 속한 집합의 리더가 같기 때문이다. 따라서 처음에 그림으로 주어진 그래프가 사이클이 있다고 판별가능하다. 왜냐하면 간선 (2, 3)을 골랐다는 것 자체가 노드 2와 3은 서로 이어져있음을 의미하는 것이기 때문이다.

• 즉 노드 2와 노드 3이 서로 다른 집합이었다면, 이 둘을 이어도(둘 사이의 간선을 그린다고 생각) 사이클은 생기지 않음. 원래 둘이 속한 집합 즉 그래프가 겹치지 않는 것이었으니까!
• 그러나 노드 2와 노드 3이 서로 같은 집합이었다면..즉 둘 사이를 잇기도 전에 애시당초 같은 그래프 안에 있던 거라면 그 둘을 잇는다는 것은 사이클을 만드는 것이 되는 것임. 

따라서 유니온 파인드로 그래프의 사이클 판단을 내릴 수 있는 것이다.

그래서 크루스칼은 결국 다음과 같은 순서로 진행한다고 볼 수 있다

1. 가장 작은 가중치를 갖는 간선을 선택한다. 
2. 그 간선에 딸린 두 노드가 같은 집합인지 판단(즉 두 노드의 리더를 비교)
3. 같은 집합이면(두 노드의 리더가 같다면) 그 간선을 선택하지 않음. 5로 건너뜀
4. 다른 집합이면(두 노드의 리더가 다르면) 그 간선을 선택. 두 노드는 union연산해줌
5. 그 다음으로 작은 가중치를 갖는 간선을 골라 2부터 반복. 모든 노드들이 골라질 때까지!

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

문제 요약

A장의 카드더미와 B장의 카드더미를 합칠 때는 A+B번의 비교를 한다.

여러 카드더미들이 주어졌을 때, 모든 카드가 합쳐진 더미를 만들 때 비교횟수는 어떤 순서로 카드들을 합쳐나가는지에 따라 달라진다. 이 때 최소 비교횟수는 몇인가?

순서는 임의대로 할 수 있기 때문에 카드가 나열된 순서와는 관계가 없다. 또한 카드더미의 개수가 1개만 주어질 때도 있는데 이 경우 비교횟수는 0이 됨을 알아두자.

1. 일단, 무식하게 풀어본다면?

나올 수 있는 모든 비교횟수합들을 구해서 가장 작은 값을 취하면 된다. n개의 카드더미가 있을 때, 이 중 두 더미를 골라 합치므로 가짓수는 nC2개. 이렇게 두 개를 골라 합치면 하나의 카드더미가 만들어지는 것이므로, 남은 카드더미는 n-1개가 되며 여기서 다시 2개를 골라 합친다. 즉 나올 수 있는 모든 비교횟수합은 nC2 * n-1C2 * n-3C2 * ...번이며 n은 최대 100,000이므로 문제의 제한시간인 2초 내에 통과하는 것은 힘들다. 즉 다른 방법을 모색해볼 것.

2. dp나 그리디를 의심해보자

>> 2-1. 최적부분구조를 가지는가?

Yes. n개의 카드묶음들로부터 나올 수 있는 최소비교횟수는 n개의 카드 중 2개를 골라 얻는 비교횟수와 그로부터 만들어지는 n-1개의 카드묶음들로부터 나오는 최소합 중(즉 nC2개가 있을 것이다) 가장 작은 값이 된다.

ex) 1번 더미와 2번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값2번 더미와 3번더미를 합치고 남은 n-1개의 카드더미로부터 얻는 최소값이런 것들 중 가장 작은 값이 문제가 요구하는 답이 됨

>> 2-2. 중복되는 구조가 있는가?

Sometimes Yes. k개 만큼의 카드더미가 있다고 할 때, 각각의 카드더미들의 구성이 같다면 중복된다고 판단가능. 그러나 이렇게 중복되는 상황이 항상 나올 것이라고 보장할 수 없다. 가끔 중복되는 정도라고 생각된다.

즉 DP로 접근하는 것은 그닥 효율적으로 보이진 않는다.

>> 2-3. 합법적으로 시작하는 그리디 의심. 탐욕적 선택 속성이 있는가?

사실 이 문제는 그리디 티를 팍팍 내는 문제라고 생각되며, 직관적으로 가장 작은 카드더미들부터 합치는 것이 좋을 것이라는 냄새도 솔솔 풍기는 문제지 않나 싶다. 문제에서 보여주는 예시부터 가장 작은 애들부터 합치니까. 실제로 이 문제는 가장 작은 카드더미부터 합쳐나가야 정답을 얻는다. 그러나 실전도 아니고 이렇게 연습 삼아 푸는 문제들에선 엄밀하게 그리디임을 검증하고 넘어가는 것이 좋을 것이다.그럼, 왜 그리디라고 생각했을까?

근거1. 탐욕적 선택 속성이 있다 즉 어떤 페이즈에서 내린 선택이 그 다음 페이즈의 선택에 영향을 주지 않는다.

내가 이번 페이즈의 선택에서 가장 작은 걸 취했다고 해서 다음 선택에서 가장 작은 걸 취할 수 없는 그런 상황은 없다. 늘 가장 작은 걸 취할 수 있다. 그리디 속성이 있다면 이렇게 내가 현재 내리는 선택이 이후의 선택에 영향을 주지 않는다. 살짝 헷갈렸던 것은, 내가 지금 선택하는 카드더미에 따라 다음 페이즈에 선택하는 카드더미의 구성이 달라지므로 "이 상황은 내가 지금 내리는 선택이 뒤에 영향을 주는 상황이 아닌가?"했지만, 정확히는 뒤에 내리는 선택에 영향을 주지 않는다가 맞지 않나 싶다. 이 문제를 통해 배웠음. 예를 들어 1309번 동물원 문제의 경우, 내가 왼쪽에 있는 칸에 사자를 배치하기로 했으면 다음 줄의 왼쪽 칸에는 사자를 배치할 수 없다는 식으로 내가 현재 내린 선택이 뒤의 선택에 영향을 주는 부분이 존재했다. 암튼 간에 이 1715번 카드 정렬하기 문제는 내가 현재 페이즈에서 내리는 선택에 다음번 페이즈에서 내리는 선택에 영향을 주지 않으므로 그리디 속성이 있다고 볼 수 있다.

근거2. 그리디는 한 번의 선택들이 그 자체로 부분문제가 된다.

스터디에서 배운 그리디의 특성이다. 제일 작은 것 2개를 고른다고 할 때, 내가 고른 두 개의 카드더미들로 인해 하나의 카드더미가 새로 만들어지고, 그 n-1개의 카드더미들로부터 또 2개를 고른다는 부분문제가 된다. 즉 한 번의 선택들이 그 자체로 부분문제가 되는 속성 역시 찾아볼 수 있었다.

3. 그렇다면, 그리디의 정당성 검증은?

지금 나는 처음에 가장 작은 카드더미들을 고른 경우를 포함하는 최적해가 있다고 생각하고 있으며, 이를 검증해야 한다. 귀류법을 통해 수학적?으로 검증해보자.

n장의 카드묶음이 있을 때, 매 선택마다 임의의 카드묶음 2개를 골라 합쳐나갔을 때 나오는 각각의 비교횟수들이 있을 것이고 총 n-1번의 비교를 한다. 이 때 가장 작은 카드묶음 2개를 골라나갈 때 나오는 비교횟수들의 집합을

G = {g1, g2, g3, ..., g(n-1)}

이라 하고, 이 문제의 최적해의 비교횟수 집합을

O = {o1, o2, o3, ..., o(n-1)}

이라 해보자. 이 때 G가 이 문제의 최적해가 아니라면 sum(G) > sum(O)가 되야 한다. 그러나 실제로는 G가 가장 작은 카드묶음이므로 sum(G) < sum(O)가 되니 가정에 모순이다. 따라서 G는 이 문제의 최적해이다.

4. 끝나지 않은 문제

작은 애들부터 골라야 한다는 것을 증명했으니, 이젠 코드만 세우면 된다. 그러나 문제가 있다. 우선 오름차순으로 카드를 정렬하고 거기서 카드더미를 2개씩 골라 합쳐나갈 텐데, 이렇게 합쳐지는 카드를 그대로 두면 전체 카드더미가 오름차순 유지가 되지 않는다. 따라서 매번 고를때마다 다시 정렬을 해주거나 적절한 위치에 새로 만들어진 카드더미를 삽입해야 한다. 그러나 정렬의 시간복잡도는 O(nlogn)이고 삽입(리스트의 insert메소드)의 시간복잡도는 O(n)이므로, 정렬이 아니라 계속 합칠 때마다 적절한 위치에 삽입을 해준다고 해도 러프하게 생각하면 최악의 경우 O(n^2)만큼의 연산을 해야 하게 되며 n은 최대 100,000이므로 이 경우 시간초과가 날 것이다). 어떻게 해야 하는가..

5. 해결책은 heapq : 우선순위 큐

일반적인 큐는 FIFO를 만족하지만, 우선순위 큐는 그와 달리 데큐를 할 때 우선순위가 높은 애들이 먼저 나온다. 즉 이 문제에선 가장 작은 카드더미들에게 높은 우선순위가 있다고 하여 우선순위 큐를 쓸 수 있다. 파이썬에서 heapq의 pop의 시간복잡도는 O(1), push의 시간복잡도는 O(logn)으로 전체 시간복잡도는 최대 O(nlogn)정도가 되고 100,000이어도 160만번 정도의 연산만 하면 되므로 시간 내에 통과가 가능해진다. 따라서, 드디어 코드는 다음과 같다.

import heapq

N = int(input())

data = []

for _ in range(N):
    heapq.heappush(data, int(input()))

answer = 0

while len(data) != 1:
    min1 = heapq.heappop(data)
    min2 = heapq.heappop(data)
    heapq.heappush(data, min1 + min2)
    answer += (min1 + min2)

print(answer)

그리디 검증 관련 참고

1. http://v2everything.blogspot.com/2015/09/greedy-algorithm.html

2. https://gazelle-and-cs.tistory.com/59

브루트포스 알고리즘은 사실 설명하기 민망할 수 있을 정도로 직관적이다. 가능한 모든 경우를 따져가며 답을 찾는 방식. 따라서 시간만 충분하다면 이 방식으로 찾은 답은 정답임이 보장된다. 모든 경우를 다 따져본 거니까..

ex - 1) 1부터 N까지의 합은?

: 무식하게 풀자면, 1부터 N까지 숫자들을 하나하나 다 더해보면 됨. 시간은 좀 걸리지만 100% 확실한 정답을 보장.

sum = 0
for i in range(1, N + 1):
	sum += N

ex - 2) 주어진 배열에 x라는 수가 있는가?

: 무식하게 풀자면, 주어진 배열의 원소를 순서대로 순회해보면 된다. 모든 원소를 순회해보면 있는지 없는지 100% 따질 수 있다.

N = 100

def solution(N, arr):
	for i in arr:
    	if i == N:
        	return True
    return False

이 방법의 최고 장점은 100% 확실한 답을 보장한다는 것. 그러나 단점은 시간이 오래 걸릴 확률이 매우 높다는 것! 

최근 알고리즘 스터디를 시작했는데, 문제를 푸는 방법에 대해 설명을 들었다. 다음과 같다.

1. 우선 무식하게 접근해보기. 즉 브루트하게 풀려면 어떻게 할 수 있나 설계해보기

2. 설계한 브루트 방식의 시간복잡도를 계산해보고, 주어진 문제의 시간제한 내에 풀 수 있을 것 같으면 코드로 옮기기

3. 시간 내에 풀 수 없을 것 같으면 다른 방식으로 해보기. 설계했던 브루트한 방식을 어떻게 최적화할 수 있을지도 고민하기.

참고로 c++언어는 대략 1억번의 연산을 1초 내로 할 수 있고, 파이썬 언어는 대략 5천만번의 연산을 1초 내에 할 수 있다고 한다. 따라서 설계한 브루트한 방식의 시간복잡도가 O(n^2) 뭐 이런 식으로 나왔다면, 여기에 문제에서 n의 최댓값으로 주어지는 값을 넣어봐서 시간 내에 충분히 될 것 같으면 코드를 짜보라는 것. 참고로 애매하게 음 한 1억번 정도 연산할 것 같은데? 로 되지는 않고 100억번 정도  연산하네? 또는 100만번만 연산하네? 정도로 확실하게 주어진다고 한다.

분리집합(Disjoint Set)이란 서로 중복되지 않는 부분집합들로 나뉜 원소들에 대한 정보를 다루는 자료구조이다. Union-Find 알고리즘은 이 자료구조를 활용하는 대표적인 그래프 알고리즘 중 하나로, '합집합을 찾는다'라는 의미를 가진다. 디테일하게 들어가면 원소 x, y를 고른 다음 x가 속한 집합과 y가 속한 집합이 같은지 판별하는 알고리즘안대, 이는 여러 노드가 존재할 때 내가 선택한 임의의 두 노드가 서로 같은 그래프에 속하는지 판별한다는 것과 같은 개념으로 생각할 수 있다.

그냥 내가 이해한대로 쉽게(나름대로) 설명하자면, Union-Find알고리즘과 분리집합은 집합을 표현하는 하나의 형태이다. 1부터 5까지의 원소들이 있고 이들이 각각 집합의 형태를 이루고 있다고 하자. 즉,

{1}, {2}, {3}, {4}, {5}

이렇게 있는 것이다. 근데 이를 표를 통해 다음과 같이 표현할 수 있다.

{1}의 입장에서 자기가 속한 집합의 리더는 자기 자신(1)이고, {2}나 다른 애들 입장에서도 마찬가지다. 즉 표를 통해 자신이 속한 집합의 리더를 나타내준것! 근데 여기서 {1}과 {2}가 만나서 합집합 {1, 2}를 만들어냈다고 하자. 1과 2가 같은 집합의 원소로 구성된 것이다. 현재 존재하는 집합들은

{1, 2}, {3}, {4}, {5}

인 것이다. 이는 방금과 같은 표를 통해 어떻게 표현할 수 있을까?

다른 건 변함없고 2만 변화가 생겼다. 자신이 속한 그룹의 리더가 1이 된 것! 사실 뭐 2를 리더로 할 수도 있지만..집합을 이루는 원소 중 가장 작은 놈을 리더로 뽑는 것이다. 쉽게 생각해서 2는 1이 이끄는 집합의 멤버가 된 것이라고 생각해도 된다. 만약 다른 애들도 서로 합치고 지지고 볶고 해서 집합들이 다음과 같이 됐다면?

{1, 2}, {3, 4, 5}

표는 다음과 같아질 것이다.

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 2랑 4다. 이들이 각각 속한 집합은 같은가?

표를 통해서 다르다는 것을 알 수 있다. 왜 Why? 2는 1이 이끄는 집합에 속해있고, 4는 3이 이끄는 집합에 속해있기 때문이다. 서로가 속한 집합의 리더가 다르기 때문에 이들이 속한 집합은 서로 다른 집합이다라고 말할 수 있는 것이다. 이것이 Union-Find알고리즘이다. 

근데 Union Find알고리즘은 여러 노드가 존재할 때 두 노드를 선택해서 이 두 녀석이 같은 그래프에 속하는지 판별하는 것으로도 이해할 수 있다고 했다. 간단하다. 단지 집합으로 표현하던 걸 그래프로 나타낼 때 Union Find가 저렇게 표현될 뿐이다. 1~5까지의 각 원소들이 집합의 형태를 이루고 있는 상태를, 1~5까지의 노드들이 서로 연결되지 않고 존재하는 상태라고 이해하면 된다. 그리고 집합들이 합쳐지는 것은 노드들 간에 연결선이 생겨서 연결되는 것으로 생각하면 된다. 따라서 내가 고른 임의의 두 노드가 서로 같은 그래프에 존재하는지 확인하는 것은 각각의 root노드들을 확인해서 같으면 같은 그래프 상에 존재하는 것이다! ...사실 이 부분은 글로만 써서 이해가 잘 안 될 수도 있으니 공부할 때 참고한 나동빈 님의 영상을 링크로 걸어두겠다.

https://www.youtube.com/watch?v=AMByrd53PHM 

그럼 Union Find를 파이썬으로 구현해보자.

parant = [i for i in range(n + 1)]

def getParant(x):         # x의 부모를 리턴하는 함수
    if parant[x] == x:    # x의 부모가 자기자신이라면 x를 그대로 리턴
        return x        
    parant[x] = getParant(parant[x])  # x의 부모가 자기자신이 아님 -> 재귀호출로 x의 부모 재설정
    return parant[x]                  # 최종적으론 x의 부모 리턴
    
def union(x, y):        # x가 속한 집합과 y가 속한 집합 합치기 - 가장 부모을 비교해 더 작은 쪽으로 합침
    x, y = getParant(x), getParant(y)
    if x < y:           # x가 더 작으니까 y의 부모를 x로
        parant[y] = x
    elif x > y:         # y가 더 작으니까 x의 부모를 y로
        parant[x] = y

def hasSameParant(x, y):         # x, y가 같은 부모를 같는지 즉 같은 집합에 속해있는지
    x, y = getParant(x), getParant(y)
    if x == y:
        return "YES"
    else:
        return "NO"

리더로 표현하던 것을 부모로 표현하는 것에만 차이가 있다. getParant함수가 이 알고리즘의 핵심으로 자신의 부모가 자기자신이 아니라면 재귀호출을 통해 자신의 부모를 최상단 노드, 즉 집단 내에서 가장 작은 놈으로 설정해준다.  이를 통해 백준 사이트에서 대표적으로 다음과 같은 문제를 풀 수 있다.

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

그래프같은 걸 탐색할 때, 너비를 우선으로 탐색을 진행하는 것을 너비우선탐색, 영어로는 Breadth First Search라고 하며 줄여서 BFS라고도 부른다. 어떠한 시작점이 있을 때, 그로부터 가까운 것들부터 탐색해나가는 방법으로 맹목적인 탐색을 할 때 사용가능한 방법이다. 이 녀석은 '최단 경로'를 찾아주기 때문에 최단길이를 보장해야 할 때 많이 쓰인다.

예시)

이 방법을 구현하려면, 큐(queue)가 필요하다.

그럼 이걸 파이썬으로 구현해보자.

우선 그래프는 다음과 같이 딕셔너리 형태로 표현해봤다.

graph = {
    1 : [2, 3, 4],
    2 : [1, 3],
    3 : [1, 2, 4, 5],
    4 : [1, 3],
    5 : [3, 6],
    6 : [5]
}           # 키에 연결된 value에 있는 리스트가 그 key에 연결된 애들임

그리고 BFS를 도와줄 큐는 다음과 같이 해보자.

queue = []                       # 큐를 리스트 형태로 구현

queue.append(something)          # 큐에 요소를 넣는 동작 : append  ->큐의 뒤쪽에 추가
queue.pop(0)                     # 큐에 요소를 빼는 동작 : pop(0)  ->큐의 앞쪽에 있는 걸 뺌

 그럼 BFS를 다음과 같이 만들 수 있다.

def BFS(graph, start_node):
    visited = []                           # 방문한 요소들이 이 리스트에 저장됨
    queue = [start_node]                   # 큐

    while queue:                           # 큐에 뭔가 있는 동안 이하 내용을 반복한다
        node = queue.pop(0)                # 큐의 제일 앞에 있는 놈을 빼와서
        if node not in visited:            # 만약 이 놈이 방문한 적이 없다면
            visited.append(node)           # 방문처리
            print(node)                    # 그 녀석 출력
            queue.extend(graph[node])      # 그 녀석과 연결된 요소들(graph[node])를 queue에 추가

근데 이 방법에는 문제점이 있다.

그것을 확인하기 위해 다음과 같이 코드 중간중간에 print를 써서 현재 queue와 visited에 있는 값들을 하나하나 확인해보고,  걸리는 시간까지 알아보자.

import time

def BFS(graph, start_node):
    start = time.time()
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            print(f'방문 처리 후 visited : {visited}')
            queue.extend(graph[node])
            print(f'큐에 연결된 요소 추가 후 queue : {queue}')
        print("-"*10)
    print(time.time()-start)

대략 0.007초가 걸렸다.

이 코드의 문제점은 그럼 뭘까?

어떤 요소를 방문처리해주고(visited.append(node))

그 요소와 연결된 요소들(graph[node])를 큐에 추가해줄 때, 방문한 적 없는 요소들만 추가해야 한다.

근데 위 코드는 일단 연결된 요소들 전부 큐에 추가해주고, 나중에 큐에서 꺼낼 때 꺼낸 값이 방문한 적이 있는지 없는지를 판단하기 때문에 쓸데없이 시간을 낭비하는 꼴이 된다.

그래서 다음과 같이 바꿔줄 수 있다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            for nd in graph[node]:             # 연결된 요소들에 대해 하나하나 따진다
                if nd not in visited:          # 방문한 적 없는 요소여야
                    queue.append(nd)           # 큐에 추가

그러나 이 방법도 문제점이 있다. 큐에 원소들을 추가해주는 작업을 하는 부분을 보면 graph[node]에 해당하는 리스트의 원소들을 루프문으로 돌기 때문에, 시간낭비가 역시 생길 수 있다!

이 문제점을, set이라는 자료형를 사용해 상당히 간편하게 해결할 수 있다.

그래서 다음과 같이 해준다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            queue += (set(graph[node]) - set(visited))

그러나 아직까지도 문제가 있다..ㅋㅋㅋㅋㅋㅋ

큐에서 제일 첫 번째 녀석을 빼주는 queue.pop(0)이 문젠데, 이 녀석의 시간복잡도가 O(n)이라는 것.

이는 collection 라이브러리에 있는 deque를 사용해 해결가능하다.

그리고 visited가 리스트로 되어있는데,

if in 또는 if not in방법은 리스트에서 하면 이 역시 시간복잡도가 O(n)이다.

따라서 visited를 딕셔너리 또는 집합(set)으로 해주는 게 더 빠르다!

그래서, 다음과 같이 해주자.

from collections import deque

def BFS(graph, start_node):
    visited = {}
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited[node] = True
            print(node)            
            queue += (set(graph[node]) - set(visited))