우선 프로그래머스 알고리즘 문제를 풀이하다가 해당 문제는 그래프 탐색 알고리즘에서 깊이 우선 탐색(DFS)로 문제를 풀어야한다는 것을 깨닫게 되었다.
프로그래머스-전력망을 둘로 나누기
추후 해당 문제에 대한 풀이도 함께 업로드할 예정이다.
그래프 탐색 알고리즘이란
그래프라는 자료 구조에서 특정한 목적지를 찾거나, 특정한 조건을 만족하는 노드를 찾는 작업을 수행하는 알고리즘.
그래프는 노드와 간선으로 이루어진 네트워크 형태의 자료 구조
노드(Node)
- 그래프의 기본 요소로 어떠한 개체나 개념
- 위 프로그래머스 문제에서 송전탑을 노드라고 할 수 있다.
- 정점(Vertex)라고도 함.
간선(Edge)
- 노드들을 연결하는 선. 노드간의 관계
- 간선은 방향성 유무에 따라 방향 그래프 & 무방향 그래프로 나뉜다.
- 위 프로그래머스 문제에서 송전탑(노드) 사이의 전력망을 간선이라고 할 수 있다.
*그래프 알고리즘을 공부하게되니 자료구조와 알고리즘에 대해 정리를 해야될 필요성을 느꼈다. 이 또한 추가해야되겠다.
인접 행렬 & 인접 리스트
그래프를 구현하는 방식으로는 인접 행렬과 인접 리스트로 2가지가 있다.
인접 행렬(Adjecency matrix)
- 2차원 배열을 사용하여 그래프를 표시
- 행과 열은 그래프의 노드를 나타내고, 행과 열의 교차점에는 노드 간의 연결 여부를 나타내는 값이 들어간다. (*주의점: 행과 열 자체는 노드를 나타내지만, 교차점의 값은 노드 간의 연결여부를 나타내는것이지 간선을 나타낸다는 아니다.)
// 방향이 없는 무방향 그래프
A -- B
| |
C -- D
// 인접 행렬
A B C D
A 0 1 1 1
B 1 0 0 1
C 1 0 0 1
D 1 1 1 0장점
- 빠른 연결 여부 확인
예를 들어, 인접행렬 matrix에서 matrix[x][y] 값이 1이면 노드 x와 y는 연결되어있음을 확인할 수 있다. - 간선의 가중치 표현
행렬로 보았을 때, 1이면 노드 간의 연결이 되었다는 것이고, 2,3,4.. 등이 된다면 간선의 가중치를 확인할 수 있다.
단점
- 메모리의 사용량이 크다.
노드의 수가 많고 간선의 수가 적어도, 행렬의 값이 0으로 존재하므로, 메모리를 낭비하게된다. - 불필요한 정보 저장
무방향의 그래프의 경우 대각선을 기준으로 대칭이므로 중복된 정보를 저장한다.
인접 리스트 (Adjacent list)
- 각 노드에 연결된 노드들의 리스트를 저장하는 방식
// 방향이 없는 무방향 그래프
A -- B
| |
C -- D
// 인접 리스트
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]장점
- 메모리 사용량이 작다.
각 노드에서 연결된 노드들의 리스트를 저장하므로 불필요한 정보를 저장하지 않는다. - 간선의 열거가 용이하다.
각 노드에서 연결된 노드들을 저장하므로, 특정 노드와 연결된 노드들을 찾는데 용이하다.
단점
- 연결 여부 확인이 느리다.
노드간의 연결됨을 확인하기 위해 특정 노드와 연결된 노드들의 리스트를 순회해야하므로 시간이 걸린다. (위의 예시에서 A와 B가 연결되어있음을 확인하려면 A의 인접 리스트를 모두 확인하여 B가 있는지 확인해야된다. 여기서 시간복잡도가 O가 된다.*시간복잡도는 별도로 내용 정리) - 간선의 가중치 표현이 어렵다.
실제로 가중치를 표현하기 위해서는 간선의 정보에 튜플(tuple)이나 객체(object)를 사용한다.
// 간선의 가중치 예시 (tuple사용)
"A": [("B", 2), ("C", 1)],
"B": [("A", 2), ("D", 4)],
"C": [("A", 1), ("D", 5)],
"D": [("B", 4), ("C", 5)]방식에 따른 선택 상황
인접 행렬
- 그래프가 밀집 그래프(간선의 수가 노드의 수에 비해 많은 경우)일 때
- 노드 간 연결 여부 확인이 빈번하게 일어날 때
인접 리스트
- 그래프가 희소 그래프(간선의 수가 노드의 수에 비해 적은 경우)일 때
- 메모리 사용량을 최소화해야할 때
- 노드 간 연결 여부 확인이 상대적으로 적게 발생할 때
my name is hyeon