그래프 ) 배열 데이터로 정제하기

작성일 In Views: Disqus:

코딩테스트에서 그래프와 관련된 문제를 만났을 때, 해당 그래프를 순회하고 조작할 수 있는 정제된 형태의 데이터로 만들 필요가 있습니다. 이번 포스트에서는 여러 그래프의 종료들의 분석하는 방법과 함께 그래프 정보를 인접행렬 / 인접리스트 데이터로 정제하는 방법에 대해 다뤄보겠습니다.

▪︎ 무방향 그래프

image.png

무방향 그래프는 노드가 서로 양방향으로 연결되어있는 형태로 방향에 상관없이 연결된 노드에 접근이 가능한 구조입니다. 행을 타겟 노드로, 열을 접근할 노드로 하는 인접행렬 데이터를 배열로 만들어 순회할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 무방향 그래프
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [2, 4],
  [2, 5],
  [3, 4],
];
const graph = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input.forEach((array) => {
  graph[array[0]][array[1]] = 1;
  graph[array[1]][array[0]] = 1;
});

console.log(graph);

▪︎ 방향 그래프

image.png

방향 그래프는 노드가 단방향으로 연결되어있는 형태로 한쪽 방향으로만 연결된 노드에 접근할 수 있습니다. 입력된 그래프 데이터에서 노드가 가리키는 다른 노드의 위치에 대한 정보만을 인접행렬에 저장합니다. (입력 데이터 각 배열의 인덱스의 값의 순서가 의미를 가집니다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 방향 그래프
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [3, 4],
  [4, 2],
  [2, 5],
];
const graph = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input.forEach((array) => {
  graph[array[0]][array[1]] = 1;
});

console.log(graph);

▪︎ 가중치 그래프

image.png

image.png

가중치 그래프는 노드끼리에 연결에 가중치가 붙어있는 구조입니다. 입력 데이터에 [1, 3, 3]과 같이 가중치에 대한 정보가 추가로 들어있습니다. 구현 방법은 위와 같으며 연결된 노드에 1이 아닌 가중치를 저장해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 가중치 무방향 그래프
const N = 5;
const input1 = [
  [1, 2, 2],
  [1, 3, 4],
  [2, 4, 2],
  [2, 5, 5],
  [3, 4, 5],
];
const graph1 = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input1.forEach((array) => {
  graph1[array[0]][array[1]] = array[2];
  graph1[array[1]][array[0]] = array[2];
});

console.log(graph1);

/* --------------------------------------------------------------------- */

// 가중치 방향 그래프
const input2 = [
  [1, 2, 2],
  [1, 3, 4],
  [3, 4, 5],
  [4, 2, 2],
  [2, 5, 5],
];
const graph2 = Array.from(Array(N + 1), () => Array(N + 1).fill(0));

input2.forEach((array) => {
  graph2[array[0]][array[1]] = array[2];
});

console.log(graph2);

▪︎ 노드 개수가 많을 때

노드의 개수가 적을 때에는 인접 행렬 데이터로 변환하여 문제를 풀 수 있지만, 노드의 개수가 많아질수록 그래프 크기가 커져 재귀의 동작이 많아져 문제를 푸는데 어려움이 생깁니다. 이럴 때는 인접행렬 대신 인접리스트를 사용하여 문제를 풀 수 있습니다.

image.png

인접리스트에서는 graph의 행의 인덱스 만이 노드를 키값으로 의미를 지니게 되고, 열의 인덱스는 인접행렬과 달리 의미를 지니지 않습니다. 각 노드 행에 연결된 노드에 대한 정보를 push해주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 인접리스트
const N = 5;
const input = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 1],
  [2, 3],
  [2, 5],
  [3, 4],
  [4, 2],
  [4, 5],
];
const graph = Array.from(Array(N + 1), () => Array(0));

input.forEach((el) => {
  graph[el[0]].push(el[1]);
});

console.log(graph);