[코드잇-자료구조3 : 그래프의 구조와 탐색] 2. 그래프 탐색

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 세번째 주제인 '그래프의 구조와 탐색'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/graphs

---

1. 그래프 탐색이란?

그래프 탐색

보통 자료구조에서 말하는 탐색 : 주어진 조건을 만족하는 데이터를 찾아내는 것

그래프 탐색 : 하나의 노드를 시작점으로 해서 연결된 노드들을 모두 찾는 것을 의미

- 그래프를 탐색할 때 시작점 노드는 우리가 정하기 나름

- 그리고 이 시작점으로부터 다른 노드들을 찾아가는 것

- 그래프의 구조에 대해 의미 있는 정보들을 알아낼 수 있음

순회 : 자료 구조 안에 저장된 모든 데이터를 도는 것
- 그래프 탐색도 하나의 노드에서 연결된 모든 노드를 다 돌기 때문에 어쩔 때는 그래프 순회라고도 부른다.
- 그래프 탐색, 그래프 순회 둘 다 같은 말이지만 본 강의에서는 '탐색'으로 표현할 예정

그래프 탐색 활용 예시

① 주어진 두 노드가 경로를 통해 연결 됐는지 안됐는지를 알아낼 수 있음

 

A와 B,C,D는 서로 연결되지 않았음

 

② 그래프에서 두 노드 사이의 최단 경로를 구함

- 최단경로 : 두 노드 사이에 존재하는 모든 경로 중 가장 거리가 짧은 경로

- 아래와 같이 친구 관계 그래프가 있으면 두 사람 사이 몇 다리를 건너서 친구인지를 알아낼 수 있는 것

 

③ 기타 정렬 등에서도 활용됨

BFS와 DFS

- 각 노드를 어떤 순서로 탐색하는지에 따라 BFS, DFS로 나뉨 (본 장 주제)

2. BFS(Breadth First Search) 개념

BFS란?

- Breadth는 너비를 뜻하는데, BFS는 너비를 우선적으로 놓고 탐색하는 알고리즘임.

그래프에서 너비를 우선적으로 탐색하는 과정

- 노드 A에서 탐색 시작

- 회색 : 탐색 마친 노드들

- 탐색한 노드들의 인접한 노드들을 계속 탐색 : A → B → C → ... → J

- 시작점에서 가까운 노드들을 먼저 탐색

- 그래프를 봤을 때 수평적으로, 깊이 보다는 너비 우선적으로 탐색

3. 큐

BFS 알고리즘에 대해서 본격적으로 시작하기 전에 미리 알아야 할 추상 자료형 : 큐

추상자료형 큐 : 선입선출(FIFO : First-in-first-out)

추상자료형 큐

큐는
- 맨 뒤에 데이터 삽입
- 맨 앞 데이터 삭제
- 맨 앞 데이터 접근
이런 기능들을 약속하는 추상 자료형으로, 데이터 흐름이 선입선출(First-in-first-out)

 

파이썬에서 큐 사용하기

파이썬에서는 자료형 deque으로 큐를 씀

from collections import deque

queue = deque()

 

변수 queue에 빈 deque를 만들어줌

# 큐 맨 끝에 뒤에 데이터 추가
queue.append("태호")
queue.append("영훈")
queue.append("현승")
queue.append("지웅")

# 큐 데이터를 출력한다
print(queue)  # 태호, 영훈, 현승, 지웅

 

그리고 이렇게 문자열 “태호”, “영훈”, “현승”, “지웅”을 저장

print 함수를 써서 queue를 출력하면 데이터가 저장한 순서대로 있는 걸 확인 가능

# 큐 마지막 데이터를 삭제한다
# 보통 큐에서도 마지막 데이터를 삭제하면 해당 메소드가 삭제한 데이터를 리턴한다
print(queue.popleft())  # 태호
print(queue.popleft())  # 영훈
print(queue.popleft())  # 현승

# 큐 데이터를 출력한다
print(queue)  # 지웅

 

 

데이터를 삭제할 때는 popleft 메소드를 사용하면 가장 앞에 있는 데이터를 삭제 가능

보통 큐는 삭제하는 데이터를 리턴하기 때문에 가장 앞 데이터를 “추출한다” 아니면 “꺼내온다”라고도 할 수 있음

4.BFS 알고리즘

BFS 알고리즘 단계

예시를 통한 설명

- 시작점 : A 

- 알고리즘을 진행하면서 이미 방문한 노드들 : 회색 , 방문하지 않은 노드들 : 노란색

- 방문했다고 표시되면 큐에 들어감

 

- 큐에 들어있는 노드가 없어질 때까지 반복문을 돌릴 것

- 가장 앞에 있었던 A를 꺼내어 인접한 모든 노드들은 돈다. 이때 이미 방문한 노드들은 건너뛴다.

 

 

A와 인접한 노드 처리

- 노드 B는 A에 인접해있고, 아직 방문하지 않았으니 이를 방문 노드로 표시 후 큐에 넣는다.

- C도 마찬가지

- 처리 완료된 노드 A는 이제 삭제한다.

 

큐에 가장 앞 노드인 B를 꺼내어 반복 (선입선출로 C보다 빨리 들어온 B부터 탐색)

- A는 회색으로 건너뜀

- D는 아직 방문하지 않은 노드이므로 회색으로 표시 후 큐에 넣음

- 이런식의 과정을 큐에 아무 노드도 없을 때까지 반복 → A에서 연결된 노드들을 모두 찾음

 

탐색 노드 순서

-  A B C D E F G H

- 그래프가 위아래보다 옆으로 먼저 탐색 

5. (실습) BFS로 연결된 역 찾기

6. (실습) BFS 알고리즘 시간 복잡도 분석

 

7. DFS(Depth First Search) 개념

DFS

- 깊이를 우선적으로 놓고 탐색

 

- A를 시작점으로 하고 탐색 -> A에 인접한 노드인 B, D, G
  -> 더 이상 갈 노드가 없으면 길이 있는 노드까지 다시 올라가서 E, H, J → C,F, I

8. 스택

BFS에서 큐가 중요했던 거처럼 DFS에서도 추상자료형 '스택'이 중요함

추상 자료형 스택 : 후입선출(Last-in-first-out)

- 맨 뒤에 데이터 추가
- 맨 뒤 데이터 삭제
- 맨 뒤 데이터 접근
이런 기능을 약속하는 추상 자료형

source : https://www.programiz.com/dsa/stack

맨 뒤에 데이터를 추가하고, 맨 뒤에서 데이터를 삭제할 수 있는 추상 자료형

- 가장 마지막에 들어간 데이터가 가장 먼저 나오기 때문에 이런 행동을 LIFO, Last-in-first-out이라고 부르기도 함

 

 

 

파이썬에서 스택 사용하기

스택도 큐와 마찬가지로 파이썬에서 자료형 deque로 씁니다. deque를 통해 스택의 기능을 복습해 볼게요.

from collections import deque

stack = deque()
변수 stack에 빈 deque를 만들어줬습니다.

# 스택 뒤에 정보 추가: "Taeho!"
stack.append("T")
stack.append("a")
stack.append("e")
stack.append("h")
stack.append("o")

# 스택 정보를 출력한다
print(stack)  # T, a, e, h, o
그리고 이렇게 문자열 “T”, “a”, “e”, “h”, “o”을 저장했다고 할게요. print 함수를 써서 stack을 출력하면 데이터가 저장된 순서대로 있는 걸 확인할 수 있습니다.

# 스택 마지막 정보를 삭제한다
# 보통 스택에서 마지막 데이터를 삭제하면 해당 메소드가 삭제한 데이터를 리턴한다
print(stack.pop())  # o
print(stack.pop())  # h
print(stack.pop())  # e

# 스택 정보를 출력한다
print(stack)  # T, a
스택은 가장 뒤 데이터를 삭제할 수 있습니다. 파이썬 deque에서는 pop 메소드를 이용하면 뒤에서부터 데이터를 삭제할 수 있습니다. 지금은 이 메소드를 세 번 호출했으니까, 가장 최근에 타이핑한 세 글자를 입력 취소 하는 거죠. 큐를 쓸 때 배웠던 popleft 메소드와 같이 pop 메소드도 삭제하는 데이터를 리턴합니다. 마지막에는 남은 스택을 보면 가장 뒤 데이터 3개가 삭제된 것을 확인할 수 있습니다.

9. DFS 알고리즘

DFS 알고리즘 단계

예시를 통한 설명

 

1) 시작노드 A를 옅은 회색으로 표시한 후 스택에 넣는다 : 스택에 있는 노드가 없을 때까지 반복문을 돌릴 것

 

2) 스택의 가장 위 노드 A를 꺼낸 후 A를 방문한 노드로 처리

 

- A에 인접한 모든 노드들을 본다. 회색 노드 즉, 스택에 있거나 이미 방문한 노드는 건너뜀. 

 - C, B는 처음 보는 노드이므로 표시 후 스택에 넣는다. A와 인접한 모든 노드는 처리했음

 

3) 스택 가장 위에서 B 노드를 꺼낸 후 진한 회색(방문한 노드) 처리 -> B를 중심으로 인접 노드 탐색

 

- B와 인접한 노드들을 돌 것이며, 회색 노드는 건너뜀. 

 

- A는 건너뛰며, D는 처음 보는 노드이므로 표시 후 스택에 넣어줌. B와 인접한 노드들은 모두 처리함

 

4) 스택에서 가장 위인 노드 D를 꺼냄 (D : 방문한 노드로 처리)

 

 

- E, G는 처음보는 노드이므로 표시를 해준 후 스택에 넣어줌

 

5) 스택의 가장 위 노드인 G를 꺼냄 (G를 방문한 노드로 처리)

- 회색 노드는 건너뛰며, 아무것도 없이 처리 끝남.

 

6) 이런식으로 스택에 아무 노드도 남지 않을 때까지 실행하면 A에서 연결된 노드들을 모두 찾음

- 노드들이 방문 처리된 순서 : A, B, D, G, E, H, C, F, I (즉, 깊이 우선적으로 탐색)

 

10. (실습) DFS로 연결된 역 찾기

11. DFS 알고리즘 시간 복잡도 분석