패스트캠퍼스 챌린지 28일차
그래프와 탐색
그래프란?
- 자료구조로써 그래프 = 정점 (Vertex) + 간선 (Edge)
• 간선 (Edge) : 무방향 / 방향 을 나타내는 선, 가중치를 가질수도 있다
- degree = 정점 x의 차수, 정점 x에 연결된 간선의 수
모든 정점의 차수의 합 = 간선의 개수의 2배
그래프를 저장하는 대표적인 두 가지 방법
1. 인접 행렬 (Adjacency Matrix)
- 그래프를 2차원 배열로 표현하는 방법
=> 0이면 두 정점을 연결하지 않는다, 1이면 두 정점이 연결 되어있다
- int[][] adj = int new[V][V];
- O(V^2) 만큼의 공간 필요, 하지만 실제로 1인 대상은 얼마 없으므로 공간 낭비
- A와 B를 잇는 간선 존재 여부 확인 문제에서 사용
2. 인접 리스트 (Adjacency list)
- 각 정점에 대해서 갈 수 있는 정점의 정보를 리스트로 저장한다
- ArrayList<ArrayList<Integer> adj;
- O(E) 만큼 공간 필요
- A와 연결된 모든 정점 확인 문제 및 공간복잡도가 낮은 문제에 활용
그래프에서 탐색이란?
• 탐색 (Search)
- 시작점에서 간선을 0개 이상 사용해서 갈 수 있는 정점들은 무엇인가
- 탐색 결과를 기록할 배열을 만들어 사용한다.
1. 깊이 우선 탐색(Depth First Search, dfs)
-1) x 를 갈 수 있다는 걸 알고 방문한 상태
-2) x에서 갈 수 있는곳을 모두 방문
2-1) y를 이미 갈 수 있다는 사실을 안다면, 굳이 갈 필요가 없다
2-2) y에서 갈 수 있는 곳들도 확인해보라
2. 너비 우선 탐색(Breadth First Search, bfs)
-1) start에서 시작해서 갈 수 있는 정점들을 모두 탐색
-2) start는 방문 가능한 점이므로 Queue에 넣어준다
2-1) start를 갈 수 있다고 표시
2-2) 큐가 비어있다면 정지 (더 확인할것이 없다)
너비우선탐색에서의 Queue
- 방문이 가능한 정점들을 찾을 때, Queue에 해당 정점을 넣는다.
- Queue에 정점이 남았다 -> 아직 방문 가능한 점이 남아있다 or 탐색중
- Queue가 비어있다 -> 시작점에서 갈 수 있는 모든점을 찾아냈다 or 탐색 끝
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr