[원티드 프리온보딩 인턴십 백엔드6차] 4-1주차 그래프와 그래프의 순회 세션 정리

  4-1주차 세션의 주제는 그래프였습니다. 3-1주차에 공부했던 트리와 비교해보면서 트리와 그래프에 대한 개념을 명확히 할 수 있었습니다. 이번 세션을 들으면서 스스로 중요하다고 생각했던 점과 면접에서 나올만한 질문에 대해 질문과 답변 형식으로 정리해 보았습니다.

1.  그래프의 정의와 그래프가 활용되는 예시를 들어주세요.

 그래프는 연결된 객체들의 집합을 정점과 간선으로 나타내는 자료구조입니다. 그래프를 활용해 1)SNS의 팔로잉 관계  2)지하철의 노선도 3)도시와 도로 4)WWW(world wide web)등을 표현할 수 있습니다. 

2.  그래프와 트리의 차이에 대해 설명해주세요.

 그래프는 트리를 포함하는 개념입니다. 그래프 중에서 계층을 가지고 싸이클이 없는 단방향의 특수한 그래프를 트리라고 합니다. 그래프는 계층이 없기 때문에 노드와 인접한 노드로 표현하는 반면, 트리는 부모와 자식 노드로 표현하고 하나의 루트 노드를 가집니다.  그래프는 양방향의 간선을 가질 수 있고, 두 노드 사이의 간선이 여러개가 될 수 있는 반면, 트리의 간선은 단방향이며 단 하나의 간선만을 가집니다. 그래프는 임의의 한 노드에서 임의의 다른 노드로 가는 경로는 여러개가 될 수 있지만, 트리는 단 하나의 경로(모든 노드 사이에는 정확히 하나의 경로만 존재)만을 가집니다. 그래프는 싸이클을 가질 수 있지만 트리는 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 경우가 없어 싸이클을 가지지 않습니다.

 정리하자면 그래프와 트리는 방향성, 순환성, 간선의 개수, 루트 노드 존재 여부, 노드간 관계성에서 차이가 납니다.

3. 그래프의 경로와 단순경로에 대해 설명해주세요.

 임의의 한 노드에서 다른 노드로 가기 위해 거치는 간선의 집합을 경로라고 합니다. 이때 경로는 여러개가 될 수 있습니다. 중복된 노드를 거치지 않는, 한번 지나간 노드를 다시 지나지 않는 경로를 단순 경로라고 합니다.

4. 순환 그래프에 대해 설명해주세요.

 그래프 내에 하나 이상의 싸이클을 가지는 그래프를 순환 그래프라고 합니다. 싸이클은 시작 노드와 종료 노드가 동일한 단순 경로를 의미합니다. 그래프의 싸이클 판별은 dfs 혹은 union-find(서로소 집합)를 통해 가능합니다. 의존성 구조, 계층 구조에서는 비순환 그래프가 적절하고 네트워크(SNS 친구관계, 통신 네트워크 등)를 표현하는 것은 순환 그래프가 적절합니다.

5. 연결 그래프란 무엇인가요?

 무방향 그래프에서 연결 그래프란 임의의 두 노드에 사이의 경로가 항상 존재하는 그래프를 의미합니다. 임의의 한 노드에서 dfs를 통해 모든 노드를 방문할 수 있다면 연결그래프입니다.

6. 그래프를 표현하는 두가지 방법과 각 방법의 장단점에 대해 설명해주세요.

  그래프는 이차원 행렬을 이용한 인접 행렬방식과 리스트를 이용한 인접리스트 방식을 통해 표현할 수 있습니다. 인접 행렬 방식은 정점의 개수를 v라고할 때 v*v이차원 행렬에 정점 i와 정점 j가 연결되어있을 경우 1 그렇지 않으면 0으로 표시합니다.

 

 인접 행렬 방식은 간선의 개수와 상관없이 항상 v*v의 이차원 행렬을 선언하기 때문에 정점의 개수는 매우 많은데 간선은 적은 희소 그래프의 경우 메모리, 성능적으로 비효율적일 수 있습니다. 메모리를 많이 차지하고, 인접한 정점을 찾기 위해 항상 길이 v의 리스트를 확인해야하기 때문입니다. 하지만 특정 노드 A에서 B가 연결되어있는지 판단할때 O(1) 시간이 걸린다는 장점이 있습니다.

 

 인접 리스트 방식은 인접한 정점들을 리스트로 관리합니다. 희소 그래프의 경우 연결된 노드들만 관리하기 때문에 인접 행렬 방식보다 더 효율적입니다. 하지만 특정 노드 A에서 다른 노드 B로 이어진 간선이 있는지 파악하기 위해서 리스트를 탐색해야함으로 연결된 간선의 개수를 n이라고 할때 O(N)만큼의 시간이 소요된다는 단점이 있습니다.

7.  어떤 경우에 dfs를 사용하는것이 bfs를 사용하는 것보다 더 적합한가요?

 모든 경로를 탐색해봐야하는 경우 dfs,bfs 어떤 것을 사용해도 좋지만 그래프가 너무 크거나, 경로의 특징을 저장해둬야하는 경우 dfs를 사용하는 것이 좋습니다. dfs는 한번에 한 경로만 관리하기 때문에 경로의 특징을 저장하기 쉽습니다. 빠르게  bfs는 큐를  한번에 여러 경로를 관리하는데 이때 큐에 저장된 정점의 수가 너무 많아질 수 있습니다. 

 반면 최단 거리를 찾는 경우에는 bfs를 사용하는 것이 좋습니다. dfs를 사용해 최단 거리임을 판단하기 위해서는 모든 경로를 탐색해봐야하는데 bfs는 가장 가까운 노드부터 순차적으로 탐색해감으로 처음 조건을 만족하는 경로가 최단 경로임이 보장되기 때문입니다.

8. 그래프의 순회와 트리 순회의 차이에 대해 설명해주세요.

 트리는 싸이클이 없지만 그래프에는 싸이클이 있을 수 있습니다. 따라서 트리와 같은 방식으로 dfs/bfs를 수행한다면 무환 루프에 빠질 수 있습니다. 이를 방지하기 위해 한번 방문한 노드를 기록해두고, 이미 탐색한 경로는 탐색하지 않도록 하는 것이 중요합니다.

[참고] 전위 순회, 중위 순회, 후위 순회는 일반적으로 부모노드, 왼쪽 서브트리, 오른쪽 서브트리 개념이 있는 이진 트리의 dfs에서 사용되는 용어이며, 일반적인 그래프와 트리에서 순회는 dfs/bfs로 나뉩니다.

9.  최단 거리 알고리즘의 종류와 각각이 사용되는 경우에 대해 설명해주세요.

 최단 거리를 찾기 위해서는 bfs, 다익스트라, 플루이드 워셜, 벨만포드 알고리즘을 사용할 수 있습니다.

 

 bfs는 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 특정 지점에 도착할때까지 힙(우선순위큐)를 이용한 bfs를 수행합니다.

 

 다익스트라 알고리즘은 특정한 노드에서 다른 모든 노드에 대한 각각의 최단 거리를 구하기 위해 사용됩니다(결과가 길이 = 노드의 총 개수인 배열). 이때 음의 간선이 없을때만 가능합니다. 실제 GPS 소프트웨어의 기본 알고리즘을 자주 사용됩니다. 매번 가장 비용이 작은 노드를 힙(우선순위 큐)를 사용하여 선택하며 최단 거리를 갱신하므로 그리디 알고리즘에 해당합니다. O(ELogV) 시간복잡도를 가집니다.

 

 플루이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용합니다 (결과가  n * n 이차원 배열). 점화시에 따라 2차원 배열을 채워나가므로 다이나믹 프로그래밍에 해당합니다. O(V^3) 시간 복잡도를 가집니다. 

 

 벨만포드 알고리즘은 다익스트라 알고리즘과 같이 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하기 위해 사용되는데 간선이 음의 가중치를 가질 수 있을때 사용됩니다.  O(V^3) 시간 복잡도를 가집니다.

10.  최단 경로를 구해야 하거나, 가중치가 있는 그래프에서 최단 거리를 찾아야한다면

 최단 거리가 아니라 최단 거리로 갈 수 있는 경로를 찾아야한다면 각 노드까지 가는 (최단 거리, 이전 노드)를 함께 저장한다. 도착 지점부터 이전 노드를 거슬러가면 최단 경로를 구할 수 잇다.

 가중치가 있는 그래프에서 가중치가 양수라면 다익스트라 알고리즘을 사용하면 된다. 힙(우선순위큐)를 사용하여 거리가 짧은 순으로 큐에서 꺼내고, 최단 거리일 경우에만 그 노드까지의 최단 거리 값을 갱신해준다.