[묘공단] 코딩 테스트 합격자 되기 - 그래프

 

 

코딩 테스트 합격자 되기 자바편

 

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

 

0. 데이터 구조

1. 비선형 구조는 계층 구조를 가지며 대표적인 구조가 트리, 그래프가 있다.

 

2. 선형 구조는 1:1 관계로 쭉 연결 되어있는 자료구조이며 대표적인 구조로 LinkedList, 배열, 스택 등이 있다.

 

여기서 그래프는 비선형 데이터 구조에 속하며 그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조이다.

 

1. 그래프의 특징

1. 그래프의 간선은 방향성을 갖거나 갖지 않을 수 있다.

2. 데이터의 간선에 가중치를 부여할 수 있다. 노드간의 이동 시 비용을 부가 하는 정도라고 생각할 수 있다.

3. 간선을 따라서 노드를 돌고 돌다가 다시 원점으로 돌아와 같은 움직임을 반복하는 것을 의미하며 순환을 할 수도 있고

마지막 간선에 방향성이 없어서 끝날수도 있다.

 

2. 실생활에 사용되는 곳

그래프 자료구조가 사용되는 곳은 최단 경로 탐색에 사용되는 네비게이션 또는 네트워크 장비 간의 연결등을 나타내는데 사용된다.

 

3. 코드 표현 방법

인접 행렬 그래프 표현 방식과 인접 리스트 그래프 표현 방식이 있는데 책에서 인접 리스트 그래프를 다루기 때문에 해당 내용으로 진행.

 

인접 리스트로 그래프를 표현하는 방법은 2가지만 생각하면된다.

1. 배열을 선언한다.

코드 예시 ) new ArrayList[n]

이 배열의 인덱스 값이 노드(vertex)의 값이라고 볼 수 있다. 즉 배열의 인덱스가 노드의 값이 됨으로 해쉬맵의 키같은 역할을 하게된다. 배열 선언하지않고 해쉬맵으로 진행해도 무방해 보인다.

 

2. 현재 노드 연결된 다른 노드의 값과 가중치를 배열에 추가한다.

코드 예시 ) list[nodeNum].add(new Node(targetNode, val));

 

 

위에서 1. 데이터 구조에서 그래프는 비선형 구조이지만 코드에서 표현할때는 선형 구조 자료구조의 형태로 연결한 다음에 한번 더 각 인덱스에 연결된 노드 정보를 쭉 넣어 표현한다.

즉 도식화된 그림의 그래프와 코드상에 표현이 일치 하지 않기 때문에 코드로 표현할 때 이해하기가 쉽지 않다.

 

4. 그래프의 최단 경로 구하기

다익스트라 알고리즘

 

시작 노드를 설정하고 특정 노드까지의 최소 비용을 구하는 방법인데 현재의 지점에서 제일 이득이 되는 곳을 선택하는 그리디 알고리즘과 유사하다.

1. 시작 노드를 0으로 설정

2. 나머지 노드를 INF로 큰 수로 설정 

3. 최소 비용 갱신 시 직전에 머문 노드도 갱신

2. 노드 개수 -1 만큼 연산 반복

 

예시 문제 )

시작 노드 부터 모든 노드까지의 최단 거리를 순서대로 저장한 배열을 리턴한다.

 

graph 변수 

[[0,1,9], [0, 2, 3], [1,0,5], [2, 1, 1]] 

0번 인덱스에 시작 노드

1번 인덱스 이동하는 노드

2번 인덱스 가중치

 

start

0

시작 노드 의미

 

n

3

노드의 총 수

 

retrun

[0, 4, 3]

 

1. 선형 배열로 각 노드와 연결된 노드 값과 가중치 설정

 

adjust[0]	[(1, 9), (2, 3)]
adjust[1]	[(1, 9), (2, 3)]
adjust[2]	[(1, 1)]

 

ArrayList<Node>[] adjust = new ArrayList[n];

for (int i = 0; i < n; i++) {
    adjust[i] = new ArrayList<>();
}

// 각 노드에 연결된 노드 나열
for (int[] edge : graph) {
    adjust[edge[0]].add(new Node(edge[1], edge[2]));
}

 

 

2. 가중치 최소값을 담을 배열

 

시작 노드에서 시작 노드 거리는 가중치는 0이기 때문에 0번인덱스만 0으로 초기화

dist

[0, ∞, ∞]

 

// 모든 노드의 거리 값을 무한대로 초기화
Arrays.fill(dist, Integer.MAX_VALUE);

 

 

3. 우선 순위 큐 초기화

 

pq

[(0, 0)]

 

Queue<Node> pq = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.cost, o2.cost)));

 

4. 큐에서 하나씩 노드를 꺼낸다.

 

Node now = pq.poll();

 

5. 큐에서 꺼낸 노드의 가중치가 가중치 최소값 배열에 담긴 값보다 크다면 무시한다.

if (dist[now.dest] < now.cost) {
    continue;
}

 

6. 현재 노드에서 연결된 노드 값들을 반복하여 뿌린다.

 

7. 연결된 노드 중에 이전에 최소값 배열보다 작은 값이 있다면 큐에 담고 값을 최소값 배열에 값을 갱신해준다.

for (Node next : adjust[now.dest]) {

    if (dist[next.dest] > now.cost + next.cost) {
        dist[next.dest] = now.cost + next.cost;
        pq.add(new Node(next.dest, dist[next.dest]));
    }
}

 

벨만-포드 알고리즘

 

노드에서 노드까지 최소 비용을 구하는데 기존 다익스트라 알고리즘과 달리 매 단계에서 모든 간선의 가중치를 다시 확인하여 최소비용을 계산한다.

다익스트라 알고리즘에서 계산 할 수 없는 음의 가중치를 가진 그래프도 구할 수 있다.

 

예를 들어 n개의 도시를 모두 투어하는데 걸리는 최소한의 이동 시간을 잡으려고한다.

도시간의 이동시 사용하는 버스의 수는 n - 1개이며 시작 도시부터의 연결된 도시 거리와 각 도시에서 연결된 도시들의 거리를 비교하면 최소를 구할수있다.

 

 

쉽게 말해서 다익스트라 알고리즘은 현재위치에서 제일 빠른 버스를 타고 일단 이동하고 이동한 장소에서도 제일 빠른 장소를 찾는 반면 벨만-포드 알고리즘은 이동을하기 전에 먼저 현재 위치에서 갈 수 있는 모든 위치에서 경로의 가중치를 계산하여 더 정확히 계산 할 수 있다.

 

아래에서 업데이트 할시 작은 값인 경우 업데이트를 반영한다.

 

1. A 노드에서 이동한다고 가정했을때 다른 노드는 무한 값으로 초기화한다.

adjust[A]	0
adjust[B]	INF
adjust[C]	INF
adjust[D]	INF
adjust[E]	INF

 

2. A 노드에서 이동할 수 있는 모든 노드 거리 업데이트

업데이트된 노드 : B, C, E

adjust[A]	0
adjust[B]	4
adjust[C]	3
adjust[D]	INF
adjust[E]	-6

 

3.  A노드를 거쳐 B 노드에서 이동할 수 있는 모든 노드 거리 업데이트

업데이트된 노드 : D

adjust[A]	0
adjust[B]	4
adjust[C]	3
adjust[D]	9
adjust[E]	-6

 

3.  A노드를 거쳐 C 노드에서 이동할 수 있는 모든 노드 거리 업데이트

adjust[A]	0
adjust[B]	4
adjust[C]	3
adjust[D]	9
adjust[E]	-6

 

4.  A노드를 거쳐 D 노드로 이동은 불가 하기에 D는 스킵

 

5.  A노드를 거쳐 E 이동할 수 있는 모든 노드 업데이트

업데이트된 노드 : C

adjust[A]	0
adjust[B]	4
adjust[C]	-4
adjust[D]	9
adjust[E]	-6

 

이러한 반복은 n - 1 횟수만큼 진행한다.

진행되는동안 각 노드까지의 최단 거리가 업데이트된다.