그래프와 인접 행렬 & 인접 리스트

오늘은 그래프와 인접 행렬 & 인접 리스트에 대해서 공부해보았다.

알고리즘 문제를 풀 때 항상 생각하는건데...어려운 문제은 항상 경로 찾기 문제가 포함된다ㅠ.ㅠ

 

이번에는 경로찾기 문제중에서도 트리 형태가 아닌 그래프에서 경로 찾기 문제에 대해서 공부하도록 하겠다.

 

1. 그래프 : 그래프는 방향 그래프와 무방향 그래프, 가중치 방향 그래프 총 3가지!

위가 무방향 그래프, 아래가 방향 그래프

• 무방향 그래프 : 방향이 따로 없는 그래프
  • 2차원 배열로 표현하자면, 행에서 열로 가는 방향 && 열에서 행으로 가는 방향 모두 확인해야 함.

graph[a][b] = 1; 로 표현된다.
즉, 아래처럼 표현 할 수 있다.

graph[1][2] = 1; // 1번과 연결된 2번 노드
graph[2][1] = 1;
graph[1][4] = 1; // 1번과 연결된 4번 노드
graph[4][1] = 1;
graph[2][5] = 1;
graph[5][2] = 1;
graph[2][3] = 1;
graph[3][2] = 1;
graph[4][5] = 1;
graph[5][4] = 1;

이때 1번 노드와 연결된 노드는 2번 노드와 4번 노드임을 알 수 있다.
반대로 2번 노드는 1번 노드와 5번 노드, 3번 노드와 연결되어있음을 알 수 있다.

 

• 방향 그래프 : 방향 표시가 있는 그래프
  • 2차원 배열로 표현하자면 행에서 열로 가는 방향 하나만 생각해도 됨.

마찬가지로 graph[a][b] = 1; 로 표현한다.
[1,5], [2,5], [2,3] [3,4] [1,2]
graph[1][2] = 1; // 1번 노드와 연결된 2번 노드
graph[2][3] = 1;
graph[3][4] = 1;
graph[1][5] = 1; // 1번 노드와 연결된 5번 노드
graph[2][5] = 1;

이때 1번 노드와 연결된 노드는 2번 노드와 5번 노드이다.
단, 5번 노드는 다른 어떤 노드의 방향으로도 갈 수 없다(5번 노드에서 다른 노드로 가는 간선이 없음)

 

• 가중치 방향 그래프 : 방향 그래프에서 각 간선마다 일정한 값을 갖는 그래프(일종의 비용이라고 생각하면 편할듯?) 
  
  • 2차원 배열로 표현시 일반적인 방향 그래프를 생성하여 해당 배열의 값에 가중치를 넣어줌

가중치 방향 그래프

graph[1][2] = 2;
graph[2][4] = 1;
graph[1][3] = 4;
graph[3][5] = 5;
graph[5][4] = 2;

요런식으로 2차원 배열을 만든 후 2차원 배열의 값에 가중치를 넣어준다.

 

2. 그래프를 코드로 표현하기

• 먼저 기억해야하는 약칭 => Vertex : 노드, Edge : 간선 
• 방향 그래프가 주어질때 1번 노드에서 N번 노드로 가는 모든 경로의 가지 수를 출력하시오. 첫째 줄에는 노드의 수 N과 간선의 수 M이 주어진다. 그 다음부터 M줄에 걸쳐 연결 정보가 주어진다.
• 손으로 하나하나 세어서 계산하자면 아래 그래프의 경우 1번 노드에서 5번 노드로 가는 경로의 가지 수는 총 6가지
  • 1 2 3 4 5
  • 1 2 5
  • 1 3 4 2 5
  • 1 3 4 5
  • 1 4 2 5
  • 1 4 5

요렇게 생긴 그래프가 있다!

1) 인접 행렬 방식 : 인접 행렬은 2차원 배열로 그래프의 연결관계를 나타낸다.

• 인접 행렬의 장점은 구현이 쉽다는 점이다. 단순하게 2차원 배열로 만드는 방식을 사용하기 때문에..!!
• 다만 graph[i][j] 인 경우 노드 i에 연결된 모든 노드들에 방문해봐야하는 경우 graph[i][1]부터 graph[i][j] 까지 모두 하나하나 확인해야하기 때문에 시간이 많이 걸린다는 단점이 있다. 단순하게 1000개의 노드와 노드마다 2개의 간선만 있다고 한다면...1000개 노드 전부를 확인해서 어떤 노드와 이어져있는지 알아야한다.
• 코드는 아래처럼 작성할 수 있다. 설명은 주석문으로 대체한다.
• 모든 노드를 탐색하는 시간 복잡도 : O(V^2)

import java.util.Scanner;

public class Algo_8 {
	
	static int n, m , result = 0;
	static int[][] graph;
	static int[] chk;
	
	public void DFS(int v) {
		if(v == n) {
			result++;
		}else {
			for(int i=1; i<m; i++) {
				if(graph[v][i] == 1 && chk[i]==0) { 
					// 현재 노드의 위치는 v 이고, 노드 i 로 갈 수 있따면 graph = 1 이 있어야함
					// chk[i] = 0 인 경우 이미 방문하지 않았기 때문에 방문 가능
					chk[i]=1;
					DFS(i);
					chk[i]=0; // chk[i]=1 넣었던 것을 취소하고 초기화
					
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// 이전 지점으로 돌아갈 경우 chk 배열에서 체크 된 것을 해제해주어야함, 이는 이미 갔던 노드에 재방문을 최소화하기 위함
		// 예를들어 1 2 3 4 5 경로로 가는 경우 chk 배열에 모두 체크되는데 
		// 이후에는 처음부터 경로를 다시 짜서 가야함으로 이전에 체크되어있었던 chk 배열의 체크된 내용을 초기화해주어야 한다.
		
		Algo_8 algo = new Algo_8();
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt(); // 노드의 갯수
		m = scan.nextInt(); // 간선의 갯수
		
		graph = new int[n+1][m+1]; // 방향 그래프를 2차원 배열로 생성 
		chk = new int[n+1]; // 마찬가지로 1 ~ 해당 숫자 까지 체크배열에 할당하기 위함
		
		for(int i=0; i<m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph[a][b] = 1; // 방향그래프 graph[a][b]로 갈 수 있다면 체크
			
		}
		
		chk[1] = 1;
		algo.DFS(1);
		System.out.println(result);
	}
}

2) 인접 리스트 방식 : 인접 행렬은 2차원 배열로 그래프의 연결관계를 나타낸다.

• 인접 리스트 방식으로 만들면 아래 그림처럼 만들어진다.
• 맨 앞의 숫자는 해당 번호의 노드를 의미하며 총 3가지 구역으로 나눴는데 각각의 구역은 다음과 같다.
  • 첫번째 구역은 해당 노드로부터 연결된(Linked) 노드를 의미한다. 
  • 두번째 구역은 보통 가중치가 들어간다. 즉, 1 번 노드에서 2번 노드로 이동하는데 3의 가중치가 붙는다면 해당 가중치인 3은 중간 구역에 넣어진다.
  • 마지막은 더 연결된(Linked) 노드가 있는지 여부를 의미한다고 생각하면 된다. 1번 노드는 2, 3, 4 번 노드까지만 연결되어있고 더 이상의 연결은 없기에 맨 뒤 구역에 없음을 의미하는 NULL이 들어간다.

그래프를 인접 리스트 방식으로 해당 그림처럼 나온다.

• 인접 리스트는 말 그대로 List 를 사용해서 경로를 정해두고 탐색하는 방법이다. 좀 더 쉽게 이야기하자면 인접 리스트는 각 노드에 해당하는 List를 생성 후 해당 노드에서 갈 수 있는 다른 노드의 번호를 해당 리스트에 넣어준다.
• 인접 리스트 방식은 쉽게 생각해서 그래프를 LinkedList 로 만들어 표현한다고 생각하면 된다. 
• 코드는 아래와 같으며 설명은 주석문으로 대체한다.
• 모든 노드를 탐색하는 시간 복잡도 : O(V+E)

package Algorithm;

import java.util.ArrayList;
import java.util.Scanner;

public class Algo_8_list {
	static int n, m, result = 0;
	static ArrayList<ArrayList <Integer>> graph; // Integer형 ArrayList 객체를 저장하는 ArrayList => 선언
	static int[] ch; // 방문한 노드를 체크하는 체크 배열
	
	public void DFS(int v) {
		if(v==n) {
			result++;
		}else {
			for(int nv : graph.get(v)) { // 이때 nv는 v 다음 노드를 의미함, 
				if(ch[nv]==0) { // 만약 nv 노드에 방문하지 않은 상태라면
					ch[nv]=1; // 방문했음을 체크
					DFS(nv); // 그리고 다음 노드(nv) 로 넘어감
					ch[nv]=0; // 넘어갔다가 온 후에는 nv 방문 체크 해제
				}
			}
		}
	}
	
	
	public static void main(String args[]) {
		Algo_8_list algo = new Algo_8_list();
		Scanner scan = new Scanner(System.in);
		
		n = scan.nextInt(); // 노드 갯수
		m = scan.nextInt(); // 간선 갯수
		
		graph = new ArrayList<ArrayList<Integer>>(); // => 객체 생성
		
		for(int i=0; i<=n; i++) {
			graph.add(new ArrayList<Integer>()); // Integer형 ArrayList 객체 생성후 graph ArrayList에 저장
		}
		
		ch = new int[n+1];

		for(int i=0; i<m; i++) { // 1번 노드부터 사용되며 n 번 노드까지 써야하기때문에 <=
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph.get(a).add(b); // ArrayList 접근 할때는 get
		}
		
		ch[1] = 1;
		algo.DFS(1);
		System.out.println(result);
		
	}
}

 

3) 코드 실행 결과

• 첫째줄에 N = 5, M = 9 를 넣고, 방향 그래프처럼 연결 정보를 입력한다.

요렇게 실행결과가 똭! 나왔다

 

3. 추가 정보 : 추가로 확인해야할 사항

사실 인접 행렬 부분은 오히려 쉬운 편이지만, 인접 리스트의 경우는 조금 더 복잡한 형태를 띄고 있다. 늘 그렇듯 가능한 쉽게 이해해서 쉽게 설명하려고 했지만 아무래도 기본 개념이 부족하다보니...설명이 복잡해지는것은 어쩔수 없었다ㅠㅠ

가장 중요한 부분이자 이전에 내가 공부하지 않았던 ArrayList 부분을 더 공부해야한다는 것도 알았다. 이 부분은 어쨌든 한번 짚고 넘어가야함으로 다시 한번 정리하도록 하겠다.