[graph] 문제유형 3가지 : 완전탐색/MST/다익스트라

1. 완전탐색 : '친구관계' 문제

 

A 로부터 시작해서 한 명의 친구에게만 소식을 전달할 수 있다면, 최대 몇 명의 친구가 소식을 전달받을 수 있을까?

(단, 소식을 전달 받은 친구한테는 소식을 재전달 할 수 없다.)

 

A로부터 시작해서 친구들에게 동시에 소식을 전달할 수 있다고 할 때, 가장 늦게 전달받는 사람은 누구인가?

(단, 친구에게 소식을 전달하는 속도는 동일하다.)

 

---

 

그래프 순회란? : 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것

• 깊이 우선 탐색(Depth First Search, DFS)
• 너비 우선 탐색(Breath First Search, BFS)

 

---

DFS 깊이 우선 탐색

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 뱡향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법
• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가, 다시 깊이 우선 탐색을 반복해야 하므로 후입선출구조인 스택을 사용한다.
• 재귀로 썼으면 return 할 경우 이전 정점으로 갈 수 있으므로 스택은 필요없다.
• 반면, 반복문을 사용했으면 방문 저장방법이 필요하기 때문에 방문한 곳을 저장할 스택이 필요하다.

• DFS 는 스택을, BFS 는 큐를 사용한다? X 탐색방법의 차이이지 자료구조 사용의 차이가 아니다.
• 마지막 갈림길을 꺼내는 방법이 재귀이면 리턴, 반복이면 스택으로 마지막 데이터를 꺼내면 되는 것이다!

 

스택의 특성

• 선형구조로 자료 간 관계가 1대1 관계를 가진다.
• (비선형구조는 자료 간의 관계가 1대 N의 관계를 갖는다. 트리)
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. => 후입선출 (LIFO, Last-In-First-Out)
•  

DFS 알고리즘1  /  남은 다른길을 스택에 저장하는 경우  /  재귀

DFS_Recursive(G, V)
    visited[v] = True # v 방문 설정
    
    FOR each all w in adjacency(G, v) # v에 인접한 모든 w
        IF visited[w] != True
            DFS_Recursive(G, w)

시작노드가 1이고 1이 2와 3과 연결, 2가 3과 5와 연결, 3이 2와 4와 연결, 5가 2와 4와 연결.

1. DFS를 실행하면 1부터 시작하여 방문 설정을 한다. (DFS(v) 호출, 1을 넣는다.)

2. for문을 도는데, 이때 1과 인접한 2와 3 중에 2부터 확인한다. (DFS(2) 호출)

3. 2는 아직 방문하지 않았으므로 다시 DFS를 재귀적으로 실행한다. (DFS(v) 호출, 2를 넣는다.)

4. DFS(3)을 호출 -> DFS(v) 호출하여 3을 받는다. 

5. DFS(4)를 호출 -> DFS(v) 호출하여 4를 받는다.

6. DFS(5)를 호출 -> DFS(v) 호출하여 5를 받는다.

7. 더 이상 갈 곳이 없으므로 리턴한다. 갈림길 없다.

8. 더 이상 갈 곳이 없으므로 리턴한다. 갈림길 없다.

9. 더 이상 갈 곳이 없으므로 리턴한다. 갈림길 없다.

10. 더 이상 갈 곳이 없으므로 리턴한다. 갈림길 없다.

 

(방향이 있는 경우) 1 -> 2 -> 5 -> 4 //  2 -> 3

1. DFS (1) 호출 -> DFS(v) 호출, 1 받음

2. DFS (2) 호출 -> DFS(v) 호출, 2 받음

3. DFS (5) 호출 -> DFS(v) 호출, 5 받음

4. DFS (4) 호출 -> DFS(v) 호출, 4 받음

5. 리턴

6. 리턴

7. 리턴

8. DFS (3) 호출 -> DFS(v) 호출, 3 받음

9. 리턴

...

 

변형) 최소 경로의 갯수를 찾는다면? (경로 여러개 찾아야 하는 경우)

가능한 모든 단순경로를 찾는다. 중복을 허용해야 하는 경우이다.

이 때 visited 를 날리면 안되고 이전 경로를 다시 허락하기 위해

for 문 밖에서 visited[v] = False로 리셋해준다!!!

 

변형) 최소 경로의 길이를 찾는다면?

 

DFS 알고리즘2  /  남은 다른길을 스택에 저장하는 경우  /  반복

s = []  # stack, 비어있는 배열
visited = [False] * V  # 노드 수만큼 False 리스트

# 반복
STACK s
visited[]
DFS(v)
    push(s, v)
    WHILE NOT isEmpty(s) # 비어있지 않을 때 진행
        v = pop(s)
        IF NOT visited[v]
            # visit(v)
            print(v)
            visited[v] = True
            FOR each w in adjacency(v) 
                IF NOT visited[w]
                    push(s, w)
# 중복이 발생할 수 있어 미리 스택 크기를 잡기 어려움

방문했던 경로가 아닌 다음 방문가능 경로를 스택에 저장하는 방식, pop할 경우 갈림길까지 점프하듯이 한번에 돌아간다.

굳이 이전 경로 저장이 필요 없는 경우 사용할 수 있다. 더 간편하다.

다만 중복이 발생할 수 있어 미리 스택크기를 잡기 어렵다. 따라서 아래 코드처럼 수정하여 보완한다.

 

 

---

BFS 너비 우선 탐색

• 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접 정점을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용한다.

 

큐(Queue)

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
• 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 이루어지는 구조
• 큐에 삽입한 순서대로 원소가 저장되며, 가장 먼저 삽입된 원소는 가장 먼저 삭제되는 선입선출 구조
• FIFO(First In First Out)

기본연산

• 삽입 : enQueue
• 삭제 : deQueue

• Front : 저장된 원소 중 첫번째 원소
• Rear : 저장된 원소 중 마지막 원소

# 미리 크기를 정한다.
# 1. 공백 큐 생성 : createQueue()
front = rear = -1

# 2. 원소 A 삽입 : enQueue(A);
rear를 하나 증가시키고, rear가 가리키는 곳에 저장한다.

# rear == QUEUE_SIZE
EnQueue(Q, x)
    if isFull()
        QUEUE_FULL
    else
        rear += 1
        Q[rear] = x


# 3. 원소 반환 삭제 :
front를 하나 증가시키고, front가 가리키는 곳에 있는 원소를 반환.

deQueue(Q)
    if isEmpty()
        QUEUE_EMPTY
    else
        front += 1
        return Q[front]

# 4. 이렇게 반복하다 rear와 front 가 만나면 => stack이 빈 상태
# 공백상테 : front = rear
# 포화상태 : rear = n-1 (n: 배열의 크기, n-1: 배열의 마지막 인덱스)

isEmpty()
    IF front = rear:
        RETURN True
    ELSE:
        RETURN False

isFull()
    IF rear = n-1:
        RETURN True
    Else:
        RETURN False

 

BFS 알고리즘

 

# 연습단계에서는 큐 구현하기

visited = [False] * size
Que = []
BFS(G, v) # 그래프 G, 탐색 시작점 v
    큐 생성
    시작점 v를 큐에 삽입
    점 v를 방문한 것으로 표시

    WHILE 큐가 비어있지 않은 경우
        t = 큐의 첫번째 원소 반환
        # 정점에 대하여 할 일 여기서 실행 ex.목적지이면 return True, while문 나가면 return False 등.
        FOR t와 연결된 모든 선에 대해
            u = t의 이웃점
            # visited[u] = visited[t] + 1 => 특정 시작점에서 도착점까지 몇 개의 간선을 지나가지? => visited에서 A와 F값을 빼면 된.
            # visited 를 배열로 만들면, 해당 숫자가 같은 갯수를 세, 해당 시간에 동시에 소식을 듣는 최대 인 수를 구할 수 있다.
            # 각 정점까지의 최소거리의 총합은? => visited 안의 값을 다 더하고 정점의 갯수를 뺀다.
            u가 방문되지 않은 곳이면
            u를 큐에 넣고, 방문한 것으로 표시

 

DFS? BFS? 언제 사용할까?

# 경로의 갯수 찾기, 한 번씩만 방문하기 => dfs, bfs 상관없다
# 거리 => bfs
# 특정 시작점에서 도착점까지의 경로의 개수 => dfs

 

 

2. MST 최소신장트리 

 

프림 알고리즘

필요없는 간선 쳐내기

선 중에서 가장 작은 것을 고르기

시작점 0, 나머지 무한대로 배치하고 임의의 시작점 정해 경로수를 업데이트해나간다.

기존값을 덮어씌운다. (갱신)

모든 경우의 수를 찾고나서 그림을 그리는 형태

 

크루스칼 알고리즘

union을 통해 연결되어 있는 노드 중 가장 boss 노드를 루트로 연결한다.

 

 

 

3. 다익스트라 알고리즘(Dijkstra Shortcut Path)

어떤 경로로 가는게 효율적일까? 

특정 시작점에서 도착점까지의 최소거리를 구하자.

 

시작점 0, 나머지는 INF 무한대로 배치.

갈래길을 가기 위해 cost에

원래값(현재 위치의 cost)에 앞으로 갔을때의 갚을 덮어씌운다. (갱신이 아닌 누적)

 

하나의 노드가 끝나면, 그 다음으로 cost가 가장 작은 node로 간다.

방문하지 않은 노드로 가는데 cost에 더해주고, 기존의 길과 비교해서 더 작은 길을 선택한다.

 

가장 cost가 작은 노드로 시작한다.

방문체크하고, 방문하지 않은 노드로 가서 ....반복

 

- 최소 경로

- 최단 거리