[Do it!_Algorithm with Python] 5.1 그래프 기본/표현 방법

 

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python'

 

그래프의 기본

---

그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 말한다.

즉, 두 노드가 연결되어 있으면 그래프라고 말할 수 있다.

먼저 그래프의 종류를 한번 쭉 훑고 가보자

그래프 종류	개념	그림
유니온 파인드	그래프 문제에서는,사이클이 생성되는지 판별하는 알고리즘이다.
위상 정렬	이 알고리즘을 사용하기 위해서는 선 조건이 있다. 1) 전후관계가 있어야 한다. 2) 즉, 방향이 있는 그래프여야 한다. 3) 이를 위해서는 사이클이 없어야 한다 이 조건에서 그래프의 각 노드를 선형으로 정렬해주는 알고리즘이다. 단, 위상 정렬로 나오는 값이 유일하지 않다는 특징이 있다. ex) 수강신청 - 수1을 들어야 수2를 들을 수 있음 - 전후 관계, 즉 방향성이 있어야 문제를 정의할 수있다.
* 다익스트라	시작점이 있고, 다른 모든 노드로 가는 최단거리를 구하는 알고리즘이다. 하지만 한가지 제약이 있다. (음수간선 안됨) 고정된 시작점에서 다른 모든 노드로 갈 때, 간선의 가중치가 음수여서는 안된다.	*
* 벨만-포드	다익스트라와 동일하지만, 벨만-포드는 '음수 간선'도 허용한다. 다만, 이 방법은 최단거리를 구하는 방법보다는 음수 싸이클이 있는지 확인하는 문제로 많이 나온다. 만약 있다면 최단거리가 -무한대로 가게 된다. ex) 시간여행으로 과거로 돌아갈 수 있는가? 웜홀로 워프 가능?
* 플로이드-워셜	최단거리를 구하는 것은 같지만, 시작점이 고정되어 있지 않다. 임의의 모든 노드에 대해서 최단거리를 구한다. 단, 시간복잡도가 좋지 않다. 따라서 N의 수가 작고 시작점이 없는 문제에 활용된다. ex) 도시간의 최단거리 구하기 특정한 도시를 정해준 것이 아니라, 모든 도시간의 최단거리를 구할 때. 또한 도시는 100개 이하이다.
최소 신장 트리	'트리'다. 문제에 어떤 알고리즘인지 나와있으며, 그래프와 각각의 가중치가 주어진 엣지가 있다. 모든 노드들을 거쳐갈 때, 그 가중치가 최소가 되게 하는 경로를 구하는 방법이다. 즉, 최소의 비용(가중치 합)으로 모든 노드들을 연결하는 방법을 찾는다. 이를 풀려면 유니온 파인드가 필요하다. '트리'라는 것은 사이클이 있을 수 없다.따라서 사이클이 나올 수 없게끔 방지하기 위해 유니온 파인드 알고리즘이 필요하다.

* 는 모두 최단거리 알고리즘이다.

 

 

 

 

 

 

그래프 표현

---

그래프를 표현하는 방법에는 3가지가 있다.

앞으로 다양한 그래프를 표현하기 위해 필수적인 이론이므로 복습하고 또 복습하자!

 

▪️Edge List

그래프의 요소는 노드와 엣지(간선) 두가지이다.

Edge List는 이 간선을 기준으로 표현한 그래프이다.

 

1) 가중치가 없는 그래프

[시작, 종료]

화살표 방향을 기준으로 시작하는 노드는 왼쪽, 종점은 오른쪽에 위치하도록 그래프를 표현한다.

만약 방향이 없다면, {1,2} {2,1} 이렇게 둘 다 추가해주면 된다.

 

 

2) 가중치가 있는 그래프

[시작, 종료, 가중치]

 

대부분 그래프 input은 {시작, 종료, 가중치}로 들어오기때문에 edge list로 표현하기 편리하다.

하지만 이 그래프는 노드와 관련되어 있는 edge를 탐색하는데 적합하지 않다.

만약 위 그래프에서 2번 노드에서 출발하는 엣지를 검색하고 싶다, 라는 문제가 들어왔다고 하자.

그러면 A의 모든 리스트들을 탐색하여 첫번째 값이 2인지 확인해야 한다. 이 경우 시간복잡도가 좋지 않다.

( 따라서 엣지 리스트는 벨만포드나 크루스칼 문제에 사용하는 것이 더 좋다.)

 

 

▪️인접 행렬

 

2차원 배열을 이용하여 그래프를 표현한다. 노드의 개수를 N라고 할 때, NxN 행렬을 만들어 준다.

 

1) 가중치가 없는 경우

 

node i에서 node j까지의 연결이 있는 경우에는 A[i][j] 에 1을 넣어준다.

가중치 값이 없기때문에 단순히 '연결성'을 '1'로 표현해준 것이다.

 

 

2) 가중치가 있는 경우

 

위에서 1을 넣어주는 대신 가중치 값을 넣어준다.

 

하지만 이 인접행렬은 특정 노드와 관련된 엣지를 탐색하는 문제에서 두가지 문제점이 있다.

 

먼저, N번 접근해야하므로 시간복잡도가 좋지 않다.

만약 2번에서 출발하는 엣지를 찾는다고 하자.

A[2]에 바로 접근한다고 해도, A[2][1],  A[2][2],  A[2][3]...처럼 N 만큼 돌면서 연결이 있는지 확인해야 한다.

 

또한 공간 효율성이 떨어진다.

노드가 N개를 위해 NxN를 만들어야 한다. 하지만 실제 코테에서는 N이 3만이 될 수 있다.

이를 NxN 행렬을 만들면 스페이스 에러가 날 것이다. 따라서 N의 수가 작을 때 이 자료구조를 사용해야 한다.

 

 

 

🔥인접 리스트

 

사실 인접리스트를 가장 많이 사용한다.

만약 알고리즘이 노드 기준으로 탐색하는 알고리즘이라면, 인접리스트를 사용하자.

 

 

1) 가중치가 없는 경우

ArrayList<integer>[N] 로 선언한다.

이때 integer는 가중치가 없어야 하고, 배열로 선언한다는 점이 중요하다.

ArrayList는 배열과 달리 크기가 가변적이다.

하지만 integer를 통해 배열의 장점 또한 갖고있다. index로 직접 접근이 가능하므로 시간복잡도가 좋다.

 

 

2) 가중치 있는 경우 ⭐️

ArrayList<Node>[N]

가중치가 있을 때는 자료형을 클래스로 사용해야 한다.

즉, Node를 class로 선언한 후 ArrayList에 사용한다.

 

 

 

인접행렬은 채워져 있지 않은 빈공간이 생기므로 시간복잡도와 공간효율성이 좋지 않았다.

하지만 인저리스트는 빈 공간이 없기때문에 메모리 초과도 발생하지 않고, index를 통해 직접 접근이 가능하므로 시간복잡도가 우수하다.