그래프

그래프 정의

💡 그래프는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조

그래프 종류

1. 방향 그래프 vs 무향 그래프(코테에 많이 등장한다)
2. 다중 그래프 vs 단순 그래프
3. 가중치 그래프 ⇒ 다익스트라

그래프 활용

그래프 문제는 정말 많이 나온다

현실 세계의 사물이나 추상적인 개념간의 연결 관계를 표현한다.

• 도시들을 연결하는 도로망
• 지하철 연결 노선도
• 컴퓨터 네트워크
• 소셜 네트워크 분석

그래프 표현 방법

그래프 라는 것은 vertex 와 edge가 연결 됐는지 안됐는지가 중요하다

구현 방법

• 인접 리스트
• 인접 행렬
• 암시적 그래프

인접 행렬

graph = [
		[0, 0, 1, 0, 1],
		[0, 0, 0, 1, 1],
		[1, 0, 0, 0, 1],
		[0, 1, 0, 0, 1],
		[1, 1, 1, 1, 1],
]

리스트의 각 줄은 각각 몇번이랑 연결 되어있는지를 나타낸다. 예를 들면 첫번째줄을 보면 1번은 2번 인덱스와 4번 인덱스에 연결 되어있으니 3번, 5번과 연결되어 있는 것이다.

또한 자기 자신을 연결하고 있는 그래프는 없다!

하지만 1번과 3번이 서로 연결되어 있는 경우는 가능하다.

인접 행렬은 단점이 있다. 있지도 않은 간선(edge)을 표현하려고 0을 적어야 한다는것. 메모리 낭비가 심해서 코딩테스트를 할때는 인접 리스트를 쓴다.

인접 리스트

graph = {
		1: [3, 5],
		2: [4, 5],
		3: [1, 5],
		4: [2, 5],
		5: [1, 2, 3, 4]
}

인접 리스트는 더 직관적으로 표현해 줄 수 있다. 1번은 3, 5 번과 연결되어있고

2번은 4번 5번과 연결되어 있다.

암시적 그래프

코딩테스트에서 가장 많이 사용하는 종류이다. 미로찾기 문제 같은 경우 이걸로 풀 수 있다.

예를들어 벽이 1이고 길이 0이라고 하면

gragh = [
		[1, 1, 1, 1, 1],
		[0, 0, 0, 1, 1],
		[1, 1, 0, 1, 1],
		[1, 0, 0, 0, 0],
		[1, 1, 1, 1, 1]
]

이런식의 코드가 작성될텐데, 실제로 미로가 이렇게 이루어져 있지만 우리는 암시적으로 서로 연결되어있다는 것을 알 수 있는 것이다.