그래프와 탐색

그래프

그래프는 정점(Vertex)와 간선(Edge)로 이뤄져있다.

간선은 무방향과 방향, 그리고 가중치의 유무로 나뉠 수 있다.

 

---

 

차수

차수란 정점의 연결된 간선의 수를 의미함.

즉, degree(x)는 정점 x에 연결된 간선의 수를 뜻함.

모든 정점의 차수 합 == 간선 개수의 2배를 만족함.

위 조건은 시간 복잡도에 이용되기 때문에 알아야함.

 

---

 

그래프 저장하는 방법

그래프를 저장하는 방법은 인접 행렬과 인접 리스트가 있다.

 

서로 장단점이 있다.

기준은 필요 공간, 한 정점에서 다른 정점으로 갈 수 있는지, 한 정점에서 갈 수 있는 정점들을 구할 때으로 나눠봄.

 

• 인접 행렬
  • 필요 공간 : O(V^2) 
    • 정점의 개수만큼(VxV) 이차원 배열을 만들어야함.
  • 정점 A에서 정점 B로 갈 수 있는지 판단 : O(1)
    • 정점 A를 시작점, B를 도착점으로 하여 arr[i][j] 의 값으로 판단
  • 한 정점에서 갈 수 있는 정점들 : O(V)
    • 정점 A를 시작으로 모든 정점들 arr[i][0] ~ arr[i][V] 까지 판단
• 인접 리스트
  • 필요 공간 : O(E)
    • 인접 리스트는 정적으로 만들어져, 한 정점에서 갈 수 있는 정점들로만 리스트가 채워진다. 즉, 이 말은 한 정점에서의 차수만큼 공간이 필요하다. 위에서 말했듯이, 차수들의 합은 간선의 2배이다. 그래서 공간은 차수들의 합, O(2E)만큼 필요하다.
  • 정점 A에서 정점 B로 갈 수 있는지 판단 : O(min(deg(A), deg(B)))
    • 양방향 그래프라 생각하면 A의 차수와 B의 차수 중에 작은 것부터 차례대로 앞에서부터 탐색해야하기 떄문에 차수 크기만큼 시간이 걸린다.
  • 정점 A에서 갈 수 있는 정점들 : O(deg(A))
    • A의 element 개수가 A에서 갈 수 있는 정점이다.

인접 리스트를 사용할 때 enhanced-for문을 주로 사용한다.

리스트를 사용할 때, 행렬을 사용하는 것처럼 for의 범위를 N처럼 하게 되면 인덱스 오류가 생길 수 있기 때문이다.

---

 

그래프 문제 해석

그래프 문제는 정점, 간선에 대한 정확한 정의와, 간선 저장 방식을 결정해한다.

 

---

 

그래프 탐색(DFS, BFS)

그래프 탐색은 깊이 우선 탐색, 너비 우선 탐색이 있다.

위 부분은 당연히 알 것이다.

 

DFS

dfs는 재귀 형식으로 이뤄진다.

 

1. dfs의 출발점은 A정점이다. ----> O(V)

2. A정점에서 갈 수 있는 정점들 ----> 인접 행렬 : O(V), 인접 리스트 : O(deg(A))

2번이 1번의 횟수만큼 함수를 호출하기 때문에

인접 행렬일 경우 O(V^2)

인접 리스트일 경우 O(deg(1) + deg(2) + ... + deg(V)) = O(E), 여기서 또 모든 차수들의 합은 간선의 2배라서 가능.

 

BFS

bfs는 큐를 사용한다.

 

1. 큐에서 정점을 뺀다. --> O(V)

2. A정점에서 갈 수 있는 정점들(위와 같음)

 

여기서 최근에 문제를 풀면서 visit를 체크할 때, 큐에서 poll할 때 visit를 체크해줘도 되지 않을까? 라는 생각이 들어 문제를 풀었는데 TLE가 났다. 이 문제를 풀고 강의를 들었는데 이 얘기를 해주셔서 놀랬다. 

큐에서 poll할 떄, visit를 체크한다고 생각하고 위의 그래프를 탐색하는 순서를 써보면 왜 안되는지 알 수 있다.

 

아래의 사진에서 중요라는 곳이 꼭 써야하는 곳이고, q에서 poll할 때, 그 아래 visit 체크를 하게 되면 생기는 오류가 위사진과 같을 때이다.

---

 

문제를 풀 때 생각해야 하는 점

 

1. 정점과 간선을 명확히 잘 구분해야한다.

---->문제에서 정점과 간선 즉, 그래프를 직접적으로 사용한다는 말이 없을 수 있다. 이럴 떄, 정점과 간선의 정의를 정확하게 파악해야한다.

 

2. 인접 행렬, 인접 리스트로 풀건지 정하기

----> 그래프 저장 방법

 

---

정리

1. 그래프가 무엇인지 --> 정점, 간선

2. 어떻게 저장 --> 인접 행렬, 인접 리스트 각각 장단점

3. 탐색이 뭔지 --> bfs, dfs

4. 너비 우선 탐색이 가지는 최단 횟수, 최단 거리 

5. 그래프가 없지만 그래프처럼 푸는 숨바꼭질, 물통

6. 멀티 소스 bfs

---

문제

 

• 일반 그래프
  • 1260
  • 2606
  • 11403
  • 11725
• 격자형
  • 기초 
    • 2667
    • 1012
    • 11724
    • 4963
    • 3184
• Multisource BFS(시작점이 여러 개)
  • 14502
• 그래프 명시 X
  • 2251
  • 1697
• 최소 이동, 최단 시간
  • 2178
  • 7562
  • 2644
  • 18404
  • 3055
  • 1389
  • 5567
  • 3055
  • 7569
  • 2644

 

---

출처 : https://github.com/rhs0266