2주차 그래프이론, DFS, BFS

[출처] [알고리즘 강의] 2주차. 그래프이론, 인접행렬, 인접리스트, DFS, BFS, 트리순회|작성자 큰돌

 

이진트리(BT, Binary Tree)

- 정이진 트리(full binary tree): 자식 노드가 0 또는 2개인 이진 트리

- 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진 트리

마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.

- 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리

- 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리

- 균형 이진 트리(balanced binary tree): 모든 노드의 왼쪽 하위트리와 오른쪽 하위트리의 차이가 1이하인 트리

map, set을 구성하는 레드블랙트리는 균형이진트리 중 하나입니다.

 

이진탐색트리(BST, Binary Search Tree)

이진트리의 일종으로 노드의 오른쪽 하위 트리에는 "상위노드의 값보다 큰 값"이 있는 노드만 포함되고 왼쪽 하위트리에는 "상위노드의 값보다 작은값"이 들어있는 트리

Q. 이진탐색트리의 시간복잡도는 얼마일까요?

만약 위와 같이 균형잡히게 분포가 되었다면 탐색, 삽입, 삭제, 수정 모두 O(logN)

그러나. 이는 삽입 순서에 따라 달라집니다. 예를 들어 1, 2, 3 이렇게 삽입이 되어 이진탐색트리가 완성이 되었다면. 이렇게 "선형적"인 자료구조가 완성되어버립니다.

- 선형적은 직선, 비선형적은 직선이 아닌 모양을 의미합니다.

 

즉, 이진탐색트리는 삽입순서에 따라 영향을 받습니다. 그러나 삽입순서가 어떻게 되든 트리의 노드들을 회전시키는 등의 방법을 통해서 "균형잡히게 만든" 이진탐색트리에서 발전된 트리로는 AVL트리, 레드블랙트리가 있습니다.

예를 들어 map이라는 자료구조는 삽입, 탐색, 삭제, 수정의 시간복잡도가 모두 O(logN)임을 보장받는데

그 이유가 균형잡힌 트리인 레드블랙트리를 기반으로 구현되어있기 때문입니다.

---

그래프 구현&탐색 : 인접행렬

인접해있다 = 연결되어있다

그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬

0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미

1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기

 

코드로 표현하면 다음과 같음

bool a[4][4] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 0},
    {1, 0, 0, 0},
};

---

그래프 구현&탐색 : 인접리스트(adjacency list)

그래프에서 정점과 간선의 관계를 나타내는 연결리스트

다음과 같이 구현

// vector
vector<int> adj[1004];
// list
list<int> adj[1004];

 

연결리스트

- n번째 인덱스에 삽입, 삭제 : O(1)

- 마지막 요소에 삽입, 삭제 : O(1)

- 특정요소 탐색 : O(n)

- n번째 요소 참조 : O(n)

vector

- n번째 인덱스에 삽입, 삭제 : O(n)

- 마지막 요소에 삽입, 삭제 : O(1)

- 특정요소 탐색 : O(n)

- n번째 요소 참조 : O(1)

​

마지막 요소에 삽입하는 연산과 배열 탐색 연산을 자주 사용하기 때문에 벡터를 사용해도 문제없음

---

인접행렬 vs 인접리스트

V : 정점

E : 간선

 

공간복잡도

- 인접행렬 : O(V^2)

- 인접리스트 : O(V + E)

// 인접행렬
bool adj[V][V];
// 인접리스트
vector<int> adj[V];

 

시간복잡도 : 간선 한개 찾기

- 인접행렬 : O(1)

- 인접리스트 : O(V)

// 인접행렬
for(int i = 0;i < V; i++){
    for(int j = 0; j < V; j++){
        if(a[i][j]){ 
        }
    }
}
// 인접리스트
for(int j = 0; j < adj[i].size(); j++){
    cout << adj[i][j] << " ";
}

시간복잡도 : 모든 간선찾기

- 인접행렬 : O(V^2)

- 인접리스트 : O(V + E)

 

​

그래프가 희소할 때는 인접리스트, 조밀 할 때는 인접행렬이 좋다.

 

둘 중 무엇을 쓰면 될까?

- 보통은 인접리스트를 쓰면 됨. 문제에서 sparse한 그래프가 많이 나옴.

- 다만,문제 또는 코딩인터뷰에서 인접행렬로 주어진다면 그대로 인접행렬로 푸는 것이 좋다.

 

---

그래프 구현&탐색 : 맵과 방향벡터

위와 같이 주어지는 경우가 맵(map) 으로 주어지는 것

방향 벡터란 dy, dx와 같은 형태 대각선까지 추가하고 싶다면 해당 값을 넣어주면 됨

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
// 위, 오른쪽, 아래, 왼쪽
for(int i = 0; i < 4; i++){
    ny = y + dy[i];
    nx = x + dx[i];
}

---

연결된 컴포넌트 ( connected component )

연결된 하위 그래프를 말하며 연결된 하나의 덩어리라고 볼 수 있다

이 덩어리는 연결된 컴포넌트에 속한 모든 정점을 연결하는 경로가 있다. 는 특징을 가짐

즉, 연결되어있는지 아니면 연결되어있지 않는지를 토대로 연결된 컴포넌트로 나눕니다. 이러한 컴포넌트들을 번호를 붙여가며 색칠하는 알고리즘은 풀르드필(floodfill)이라고 합니다.

---

깊이우선탐색( DFS, Depth First Search )

어떤 노드부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘입니다.

// 수도 코드

DFS(u, adj)
    u.visited = true
    for each v ∈ adj[u]
        if v.visited == false
            DFS(v, adj)

어떤 정점 u를 방문했다고 표시

u와 연결된 정점 v가 이미 방문 되었는지 체크

방문되지 않았다면 그 정점을 재귀적으로 DFS

 

두 가지 방식으로 구현할 수 있음

1. 이미 방문된 정점이라면 건너뛰기

2. 일단 방문 후 방문 된 적 있는지 체크

---

너비우선탐색( BFS, Breadth First Search )

어떤 정점에서 시작해 다음 깊이의 정점으로 이동하기전 현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는 알고리즘입니다. 같은 가중치를 가진 그래프에서 최단거리알고리즘으로 쓰입니다. 참고로 가중치가 다른 그래프 내에서 최단거리 알고리즘은 다익스트라, 벨만포드 등을 써야 합니다.

 

// 수도 코드

BFS(G, u)
    u.visited = 1
    q.push(u);
    while(q.size()) 
        u = q.front() 
        q.pop()
        for each v ∈ G.Adj[u]
            if v.visited == false
                v.visited = u.visited + 1
                // 위의 코드를 v.vistited = true; 로 바꾸면 
                // v.visited에는 방문 여부만 저장되지만
                // 위와 같이 u.visited +1의 값을 넣어주면
                // 시작점에서 해당 정점까지의 최단거리를 구할 수 있게 된다
                q.push(v)

 

+ 시작 지점이 다수라면 3번쨰 줄의 q.push 를 모든 시작점에 대해 수행하면 됨

---

DFS와 BFS비교

둘 다 시간복잡도는 인접리스트로 이루어졌다면 O(V + E)이고 인접행렬의 경우 O(V^2)가 되는 것은 동일

이름	설명
DFS	메모리를 덜 씀. 절단점 등 구할 수 있음. 코드가 좀 더 짧으며 완전탐색의 경우에 많이 씀.
BFS	메모리를 더 씀. 가중치가 같은 그래프 내에서 최단거리를 구할 수 있음. 코드가 더 김

---

트리 순회 ( Tree traversal )

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말합니다. 이는 노드를 방문하는 순서에 따라 후위순회, 전위순회, 중위순회, 레벨순회가 있습니다.

후위순회 4 5 2 3 1

후위순회(postorder traversal)는 자식들 노드를 방문하고 자신의 노드를 방문

전위순회 1 2 4 5 3

전위순회(preorder traversal)는 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문

 

중위순회 4 2 5 1 3

중위순회(inorder traversal)는 왼쪽 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문

 

레벨순회

레벨순회(level traversal)입니다. 앞서 설명한 BFS