자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Graph_인접행렬)

 

11. 그래프와 인접행렬

 

그래프에 배워보고, 그 다음에 그래프를 코드안에서는 어떻게 구현하는지 알아보겠습니다.

G(V,E)로 이뤄진 집합입니다.

Graph는 vertex(정점,노드)와 edge(간선)으로 이루어진 집합

G(V,E)

 

 

 

1. 무방향 그래프

 

양방향 그래프라고 보면 됩니다. 양쪽 다 갈 수 있으면 무방향으로 하고 연결되어있다고 가정합니다.

도시라는 주제가 주어지면, 노드가 도시가 되고 간선이 도로라고 보면 됩니다.

1번에서 2번 갈 수 있고, 2번에서 1번 갈 수 있다는 것입니다.

5 5 // 정점개수, 간선 개수
1 2
1 2
2 4
3 4
2 5

 

 

프로그래머스에서 입력이 들어오면 이것을 그래프로 어떻게 구현할까요?

2차원 배열로 그래프라는 걸로 잡습니다.

 

graph	1	2	3	4	5
1	0	1	1	0	0
2	1	0	0	1	1
3	1	0	0	1	0
4	0	1	1	0	0
5	0	1	0	0	0

graph[a][b] 1;
graph[b][a] 1;

위와 같이 하면 1 2 간선 정보를 입력한 것입니다.

그리고 가장자리에 있는 숫자들은 노드 번호라고 생각하면 됩니다.

다시 말해서 2차원의 인덱스 번호가 노드(정점)번호라고 생각하면 됩니다.

 

그렇다면 어떻게 분석할 것인가? 행을 고정 시켜서 열을 탐색하면 됩니다.

1번 정점과 연결된 정점이 누구냐고 했을때 1번 행에서 체크된 것만 1번 정점이랑 연결 된 것입니다.

이런걸 인접행렬이라고 하고, 인정행렬을 가지고 그래프가 어떤 모양구나 라는걸 프로그래밍할때 분석하는 것입니다.

 

정점 개수가 많아지면 인접행렬로 했을때 무작위로 메모리 낭비도 많이되고, 시간복잡도도 복잡합니다.

그럴때 인접리스트를 사용합니다.

2. 방향 그래프

 

이동하는 방향이 정해져있다는 것으로, 1번 정점에서 2번 정점으로만 갈 수 있고 반대로는 갈 수 없습니다.

5 5 // 정점, 간선 개수
1 2 // 1번 정점에서 2번 정점으로 갈 수 있다는 의미
1 3
3 4
4 2
2 5

graph	1	2	3	4	5
1	0	1	1	0	0
2	0	0	0	0	1
3	0	0	0	1	0
4	0	1	0	0	0
5	0	0	0	0	0

 

graph[a][b] = 1;

행번호에서 열번호로 이동한다라고 해석해야 합니다.

이러한 인접행렬은 

3번 노드에서 갈 수 있는 노드가 누구냐 분석할때, 3행을 고정하고 열을 쭈욱 탐색합니다.

3번 노드에서 4번 노드로 이동하구나라고 알 수 있습니다.

 

 

3. 가중치 방향 그래프

 

방향그래프에서 간선에 가중치 값까지 있는 것입니다.

1번 노드에서 2번 노드로 이동하는데 비용이 2이다.

1번 도시에서 3번 도시로 이동하는데 물류 비용이 4이다.

 

a b c
1 2 2
1 3 4
3 4 5
2 5 5
4 2 2

graph	1	2	3	4	5
1	0	2	4	0	0
2	0	0	0	0	5
3	0	0	0	5	0
4	0	2	0	0	0
5	0	0	0	0	0

 

graph[a][b] = c;