
그래프 (재귀, 비재귀 DFS)
·
알고리즘(코딩테스트)
1. 그래프의 특징과 종류방향이 있는 그래프 가중치가 있는 그래프 순환이 있는 그래프 2. 그래프 구현2 - 1. 인접 행렬을 이용한 그래프배열의 인덱스는 노드세로 방향 출발 노드가로 방향 도착 노드배열의 값은 노드의 가중치 2 - 2. 인접 리스트를 이용한 그래프 결론인접 행렬크기가 고정되어 있기 때문에 노드가 많고 연결이 적은 그래프에서 낭비가 심한 단점이 있다.간선의 정보를 O(1)에 얻을 수 있는 장점이 존재인접 리스트대부분의 경우 인접 행렬에 비해 메모리를 절약할 수 있다.평균적으로 간선의 정보를 얻는데 시간이 좀 더 걸림 3. 그래프 탐색3 - 1. BFS최단 경로를 보장하는 탐색 방식queue를 사용한다.방문 처리를 queue에 push할때 진행한다.#include #include #i..