[게임 프로그래머 입문 올인원] 그래프와 알고리즘 : DFS, BFS (58, 59강)

A. 그래프와 알고리즘

1. DFS

a. DFS란?

🌟 Depth First Search, 깊이를 우선으로 파고 들어가는 검색방법

 

DFS, BFS 둘 다 이 이미지를 구현

 

b. DFS 생성하기

1) 인접 리스트

 

재귀함수로 생성가능 = 스택을 이용

 

먼저 그래프를 인접리스트로 생성

 

초기화 해주기

 

재귀함수를 활용해 방문도장 찍기

 

위 코드 실행결과

 

2) 인접 행렬

 

행렬 생성

 

행렬로 바꿔서 수정된 코드 (방문도장)

 

c. 모든 정점을 둘러보기

위 코드를 실행해보면 5번 정점에 대한 데이터는 얻을 수 없음 (데이터 방향이 단방향)

따라서 모든 정점에 대한 반복문을 돌려주면 모든 정점을 둘러볼 수 있음

 

된다

 

d. 시간복잡도(BFS랑 똑같음) 

1) 인접 리스트일 경우

 

모든 정점마다 한번씩 함수에 호출 (v) + 간선의 총 개수 (e)

 

간선의 총 개수는 e지만 모든 정점들이 연결되어 있으면 자체가 v제곱이 될 수 있음

따라서 간선이 드문드문 연결되어있는 데이터에 적합함!!

 

 

2) 인접 행렬일경우

 

정점마다 한번씩 함수에 들어오고 (v) * for문을 v번만큼 하기 때문(v) = v제곱

 

느리다

 

 

2. BFS 

a. BFS란?

🌟 "Breath First Search" 너비우선탐색

 

• 입구에서 얼마나 떨어져있는지, 즉 가까운 순서대로 접근 
• 가장 빠르게 발견한걸 먼저 방문 = 선입 선출 = 큐 

 

b. BFS 생성하기

큐를 사용해서 생성

 

1) 인접 리스트로 생성

 

 

dfs에서는 visited를 사용해 방문한 목록을 체크했지만

bfs에서는 discovered를 사용해 발견한 목록을 체크함 

 

먼저 false로 초기화

 

인접한 애들을 찾아서, 방문 예약을 하고 먼저 발견한 곳은 넘어가도록 (continue)

 

실행결과

 

2) 인접 행렬로 생성  

 

방문도장 부분 코드만 바뀜

 

c. 모든 정점 둘러보기 

이 코드를 실행하면 5번까지 나옴

 

d. 길찾기를 위한 추가적인 정보 넣어주기

• 누구에 의해서 발견 되었는지 : parent
• 시작점에서 얼만큼 떨어져 있는지 : dist

 

시작은 처음, 0으로 설정

 

방문도장에서 빨간박스코드 추가

 

parent : 실행해보면 발견한 경로를 알 수 있음

 

dist : 얼마나 떨어져있는지 알 수 있음

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -