[ 11장 ] 그래프

-1) 그래프의 개념

그래프는 노드와 간선을 이용한 비선형 데이터 구조

보통 데이터 간의 관계를 표현하는데 사용

데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현

간선은 방향이 있을 수도 있고 없을 수도 있음

만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현

그래프의 특징과 종류

방향성, 가중치, 순환 특성에 따라 종류 구분 가능

• 흐름을 표현하는 방향성

  방향 그래프 : 방향이 있는 간선을 포함하는 그래프
  -> 어느 한쪽으로만 간선이 있는 것이 아니라 서로 반대를 가리킬 수 있음

  무방향 그래프 : 방향이 없는 간선을 포함하는 그래프

• 흐름의 정도를 표현하는 가중치

  가중치 그래프 : 데이터의 흐름 방향 뿐만 아니라 양도 중요한 경우 가중치를 표현한 그래프

• 시작과 끝의 연결 여부를 보는 순환

  순환 그래프 : 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 그래프

  비순환 그래프 : 순환이 존재하지 않는 그래프

그래프 구현

1. 인접 행렬 그래프 표현

• 배열을 활용하여 구현하는 경우가 많음
• 배열의 인덱스는 노드
• 배열의 값은 노드의 가중치
• 행(세로 방향)을 출발 노드
• 열(가로 방향)을 도착 노드로 생각

2. 인접 리스트 그래프 표현

• 노드는 정점(v),가중치(w),다음 노드(next)를 묶어서 관리
• 노드 개수 만큼 배열을 준비
• 배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결

인접 행렬과 인접 리스트 장단점 비교
어느 한쪽이 매우 뛰어나거나 하지 않음

인접행렬의 장단점
++ 간선의 정보를 확인할 때 시간 복잡도 O(1)
++ 구현 난이도 낮음

-- 희소 그래프, 즉 노드 수에 비해 간선 수가 매우 적은 그래프일 때는 인접 행렬 공간 중 대부분의 공간이 실제 사용되지 않아서 비효율적

-- 노드들의 값의 차이가 매우 클 때, 가장 큰 노드 값 기준으로 인접 행렬 잡아야해서 비효율적

인접리스트의 장단점
++ 메모리를 아낄 수 있음

-- 특정 노드에서 시작하여 연결된 노드 개수가 많으면 많을수록 노드를 연결한 리스트의 길이만큼 탐색해야해서 탐색 시간 O(N)

보통은 시간 제약에서 장점을 취하는 행렬 방식으로 그래프 문제를 푸는 경우가 많음

문제에서 노드 개수가 1000개 미만으로 주어지는 경우에는 인접 행렬을 사용하면 됨 !

( 노드의 데이터가 숫자가 아니라 문자열이면 문자열을 숫자로 매핑하여 인접 행렬의 인덱스로 사용하면 됨 )

-2) 그래프 탐색

1. 깊이 우선 탐색 (DFS)

" 더 이상 탐색할 노드가 없을 때까지 일단 가보고, 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문 "

탐색을 하려면 일단 시작 노드를 정하고 스택에 시작 노드를 push
스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드
( 노드를 pop 하면서 방문 )

스택을 이용한 DFS 구현

1. 스택이 비었는지 확인
   스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미하니 스택이 비었으면 탐색을 종료
2. 스택에서 노드를 팝
   팝한 원소는 최근에 스택에 푸시한 노드
3. 팝한 노드의 방문 여부를 확인
   아직 방문하지 않았다면 노드를 방문 처리
4. 방문한 노드와 인접한 모든 노드를 확인
   그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시
   스택은 FILO 구조이므로 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 푸시
   ( 4->5 순으로 방문하고 싶으면 5->4 순으로 푸시 )

코드로 구현할 때 고려할 사항 세 가지
1. 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 함
2. 가장 최근에 방문한 노드를 알아야 함
3. 이미 방문한 노드인지 확인할 수 있어야 함

핵심은 " 가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다 "

탐색하고 있는 방향의 역방향으로 되돌아가는 동작을 백트래킹이라고 함
-> 스택의 특성을 활용하여 백트래킹 동작을 쉽게 구현 가능

재귀함수를 활용한 깊이 우선 탐색

스택을 직접 사용하지 않고도 깊이 우선 탐색을 구현할 수 있음

재귀함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 깊이 우선 탐색에 활용할 수 있는 것임

호출할 함수는 dfs()라고 선언하고, dfs(N)을 호출하면 다음 동작을 하도록 구현
-> dfs(N) : N번 노드를 방문 처리하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색

2. 너비 우선 탐색 (BFS)

" 현재 위치에서 가장 가까운 노드부터 모드 방문하고 다음 노드로 넘어감
그 노드에서 또 다시 가까운 노드부터 모두 방문 "

여기서 말하는 가까운 거리는 시작 노드와 목표 노드까지의 차수 ( 아래로 향하는 간선의 개수 ) 이지, 간선 가중치의 합이 아님

• 시작 노드를 정하고 큐에 시작 노드를 푸시
• 시작 노드를 큐에 푸시하면서 방문 처리
• 큐에 있는 노드는 이미 방문 처리를 했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태

1. 큐가 비었는지 확인, 큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미이므로 탐색 종료
2. 큐에서 노드를 팝
3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문 처리

코드로 구현할 때 고려할 사항 두 가지
1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 함
2. 이미 방문한 노드인지 확인할 수 있어야 함

방문 처리 시점이 다른 이유
깊이 우선 탐색은 스택에서 팝하며 방문 처리를 했고, 너비 우선 탐색은 큐에 푸시하면서 방문 처리를 함

DFS에서는 스택에 다음에 방문할 인접 노드를 푸시, 즉 스택에 푸시할 노드는 방문 예정이 노드이므로 팝하며 방문 처리

BFS에서는 지금 방문할 노드를 푸시, 그래야 인접한 노드부터 탐색할 수 있기 때문

DFS - 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야하는 경우 활용 가능
코딩 테스트에서는 탐색을 해야할 때, 최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 우선 고려하는게 좋음

BFS - 문제에 대한 답이 많은 경우 답 중에서 가장 가까운 답을 찾을 때 유용
코딩테스트에서는 미로 찾기 문제에서 최단 경로를 찾거나 네트워크 분석 문제를 풀 때 활용 가능

-3) 그래프 최단 경로 구하기 ( 다익스트라, 벨만포드 )

최단 경로는 그래프의 종류에 따라 다르게 해석됨

가중치가 없는 그래프 : 간선의 개수가 가장 적은 경로
가중치가 있는 그래프 : 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소

1. 다익스트라 알고리즘 - O(V**2)

가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용한다고 보면 됨

1. 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용과 직전 노드를 저장할 공간을 마련
   1-1. 최소 비용과 직전 노드를 저장할 공간은 모두 매우 큰 값 INF로 초기화
   1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자기 자신으로 초기화

2. 해당 노드를 통해 방문할 수 있는 노드 중, 즉 아직 방문하지 않은 노드 중 현재까지 구한 최소 비용이 가장 적은 노드를 선택
   2-1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소 비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신
   2-2. 이때 직전 노드도 같이 갱신

3. 노드 개수에서 1을 뺀 만큼 반복

다익스트라 알고리즘은 한 번 방문한 노드는 다시 방문하지 않기 때문에 ( 그리디처럼 작동 ) 음의 가중치가 있는 그래프에서는 제대로 작동하지 않음 !

2. 벨만포드 알고리즘 - O(V*E)

매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단 경로를 구할 수 있음

1. 시작 노드를 설정한 다음 시작 노드의 최소 비용은 0, 나머지 노드는 INF로 초기화
   이후 최소 비용을 갱신할 때 직전 노드도 갱신
2. 노드 개수-1 만큼 다음 연산을 반복
   2-1. 시작 노드에서 갈 수 있는 각 노드에 대해서 전체 노드 각각을 거쳐갈 때 현재까지 구한 최소 비용보다 더 적은 최소 비용이 있는지 확인하여 갱신
   ( 다익스트라에서는 연결된 거만 확인, 여기서는 전체 확인 )
   최소 비용을 갱신할 때 V의 직전 노드 값도 같이 갱신
3. 과정 2를 마지막으로 한 번 더 수행하여 갱신되는 최소 비용이 있는지 확인
   만약 있다면 음의 순환이 있음을 의미