내일배움캠프 94일차 - 자료구조 & 알고리즘 18주차 : 그래프

그래프

그래프는 점(객체)와 간선(관계)으로 이루어진 존재다.

정점(Vertex) = 동그라미, 객체 하나하나.
간선(Edge) = 선, 두 객체 사이의 관계

정점 V = {A, B, C, D, E} (5개)
간선 E = {A-B, A-C, B-D, C-D, D-E} (5개)

수학에서는 이 둘을 묶어 G = (V, E)라고 쓴다.

그래프의 구성요소

그래프는 세 가지 축으로 나뉜다.

무방향: 선이 양방향 (친구, 양방향 도로)
방향: 선에 화살표 (팔로우, 일방통행)
가중치: 선에 값 (거리, 시간 비용)

세 축은 서로 조합된다.

무방향 + 비가중치
 : 가장 단순한 그물망
 : DFS · BFS의 기본 무대

방향 + 가중치
 : 비용이 붙은 지도
 : 다익스트라의 무대

컴퓨터가 보는 세계

인간: 점과 선이 한눈에, "A랑 B가 이어져 있네"
컴퓨터: '그림'이란 게 없음. 저장할 수 있는 건 숫자와 목록 뿐.

따라서 그림속 "무엇이 무엇과 연결됐는가"를 숫자 데이터로 옮겨 적어야 한다.

★ 이 데이터가 답해야 할 질문

질문1) "둘이 연결됐는가?"
 - A와 B는 친구인가?
 - 이 역에서 저 역으로 바로 가나?

질문2) "이웃은 누구인가?"
 - A의 친구를 전부 알려달라.
 - 이 역에서 갈 수 있는 다음 역들은?

※ 앞으로 배울 모든 탐색·길찾기가 이 두 질문을 수없이 반복한다.

★ 질문에 대답하기 위한 전략

전략1) 모든 쌍의 체크표를 만든다.

점이 N개면 N×N 칸의 표.
이 표의 이름이 인접 행렬(Adjacency Matrix)이다.

학급의 "짝꿍 여부 체크표" 처럼, 가능한 모든 (점, 점) 쌍에 대해 "선이 있으면 1, 없으면 0"을 적어둔다.

세 간선의 인접부분을 모두 표에 적으면 대칭이 보인다.

단점: 표의 대부분이 0이다.
 : 점이 10만개면 100억 칸, 그마저 대부분 0임.
 : "없다"를 기억하는 데에 공간을 거의 다 쓰는 셈이다. 다른 전략이 필요함.

전략2) 내 이웃만 적는다.

0은 적지 않고, 점마다 "연결된 이웃 목록"만 들고 있다.
이 방식의 이름이 인접 리스트(Adjacency List) 이다.

C++에서는 인접리스트를 vector<vector<int>> adj 로 표현한다. adj[i]가 곧 "정점 i의 이웃들" 이다.

2차원 vector로 작성된 인접 리스트

잘하는 것
 : 메모리, 점 + 간선 수만큼만 (O(V+E))
 : 질문②인 "이웃은 누구인가?"에 대해 "목록을 그대로 읽으면" 대답이 된다.

못하는 것
 : 질문①인 "둘이 연결됐나?"에 대해 대답하려면 A의 목록을 처음부터 훑으며 B를 찾아야 한다. 
→ (O(deg)), 행렬의 "딱 한 칸 확인"보다 느림.

※ 그럼에도 거의 모든 실전 그래프는 인접 그래프를 쓴다. 현실의 그래프는 대부분 희소(점은 많고 선은 적음)하기 때문이다.

메모리 ↔ 질의 속도와 맞바꿈

※ 최선은 상황에 맞는 도구를 고르는 것. 메모리를 내주고 속도를 얻느냐, 반대냐의 맞바꿈이다.

표현했으면, 이제 해매야 한다.

그래프를 코드로 담았으니, 0에서 출발해 연결된 점들을 모두 방문한다.

방문하는 순서에는 두 가지 사고방식이 있다.

1) DFS(깊이 우선):  한 길로 끝까지, 막히면 되돌아간다.

방문 순서: {0 → 1 → 3 → 4 → 2 → 5} (한쪽으로 끝까지 간 뒤 되돌아옴)

 - 미로에서 한쪽 벽을 따라 끝까지 들어가는 느낌.

 - 재귀나 스택으로 구현한다.

 - 미로 풀이·사이클 검출에 강하다.

2) BFS(너비 우선):  가까운 곳부터 한 층씩

방문 순서: {0 → 1 → 2 → 3 → 4 → 5} (1단계 이웃 → 2단계 이웃 → …)

 - 잔잔한 호수에 돌을 던졌을 때 퍼지는 파동처럼.

 - 큐(Queue)로 구현한다.

 - 최단 거리에 강하다.

※ 같은 그래프·같은 출발점이지만 "어떤 정보를 얻고 싶은가"가 순서 선택을 결정한다.