[바킹독 알고리즘] 0x18강 : 그래프

그래프 정의

정점과 간선으로 이루어진 자료구조
간과하기 쉬운 그래프 : 루프가 존재하는 그래프, 연결 그래프가 아닌 경우 (도 생각해야한다.)

그래프 표현법

1. 인접 행렬

vertex * vertex의 2차원 배열을 만들어서 각 vertex의 간선이 존재하면 양방향일 경우 두 vertex에 각 칸을 전부 1로 세팅, 단방향일 경우 해당 칸에만 1로 set해서 그래프를 표현할 수 있다.

2. 인접 리스트

인접 리스트를 표현할 때 Kotlin에서는 LinkedList를 실제로 사용하면 되지만, C++의 경우 Vector를 사용해도 무관하다. ( 그렇다면 Kotlin에서도 Pair<Int,MutableList> 로 사용하면 되지 않을까? 싶다..)

그래프에서 BFS와 DFS

1. BFS using Queue

만약 위 예시처럼 연결그래프가 아닐 경우에는 BFS 그림 문제처럼, 모든 정점을 돌면서 아직 visit 하지 않은 정점을 시작으로 BFS를 돌려서 문제를 풀 수 있다.

2. DFS using Stack / Recursion

재귀의 경우 상대적으로 Stack보다 느리게 작동한다. 코딩테스트에서 만약 스택 메모리 제한이 존재한다면 Stack으로 푸는게 맞다. sw academy 는 1MB로 스택메모리 제한이 있다고 한다. 

모든 출처: https://blog.encrypted.gg/1016