패스트캠퍼스 챌린지 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 탐색 끝

  

 

 

 

28일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]