[Java] 그래프 이론(dfs와bfs)

코딩 테스트 문제에서 dfs(depth-first-search, 깊이우선탐색), bfs(breate-first-search, 너비우선탐색)알고리즘 문제가 빈번하게 등장한다. 이러한 알고리즘들은 보통 그래프 이론을 통해 구현한다.

그래서 그래프 이론 개념에 대해 정리하고 그래프이론을 통해 dfs, bfs를 구현 해보려고 한다. 해당 포스터에서 dfs, bfs의 개념은 다루지 않는다. 간단하게 정리하고 넘어가자면 dfs는 스택, 재귀함수를 통해 구현할 수 있고, bfs 큐를 이용하여 구현할 수 있다.

1. 그래프(graph)

수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면 사물이나 추상적인 개념간의 연결 관계를 표현한 것이라고 할 수 있습니다. 도시를 연결하는 도로망이나 사람들 간의 관계, 웹 사이트의 링크 관계 등이 이에 해당하는 예시 입니다.

코딩테스트 에서는 다양한 상황을 구현하기 위한 방법으로도 많이 사용된다.

2. 그래프 구성요소

정점(Vertex) : 그래프에서의 노드(또는 위치)
간선(Edge) : 그래프에서 노드와 노드를 연결을 나타냄
인접 정점 : 간선에 의해 연결된 정점
G(V, E) : 그래프는 정점과 간선의 집합이므로 G(V, E)는 그래프 그 자체를 의미

3. 그래프 종류

무방향 그래프
간선을 통해 양방향으로 이동할 수 있는 그래프
G(A,B)는 G(B,A)와 동일
방향 그래프
간선에 방향이 존재하는 그래프
G(A,B)와 G(B,A)는 다름
가중치 그래프
간선에 비용 또는 가중치가 할당된 그래프
'네트워크' 라고도 함
연결 그래프
무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
비연결 그래프
무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
순환 그래프
단순 경로의 시작 정점과 종료 정점이 동일한 경우
※ 단순 경로(Simple Path) : 반복되는 정점이 없는 경로
비순환 그래프
순환이 없는 그래프

4. 인접행렬과 인접리스트

그래프를 구현하는 방법으로는 인접행렬과 인접리트스가 있다. 이 두가지 방식은 각각의 장단점을 지니고 있다. 따라서 문제의 조건, 구현하려는 알고리즘, 그래프의 종류에 따라 적절하게 사용해야한다.

다음과 같은 상황이 주어졌을 때, 인접행렬과 인접리스트로 그래프를 구현해보도록 하겠다.

정점	인접 정점
1	2
1	3
1	4
2	4
3	4

위의 표와 같이 그래프의 조건이 주어진다.

4.1 인접행렬로 구현

인접행렬은 간선의 최대값을 담을 수 있는 크기만큼의 2차원 배열을 통해 구현하여 간선으로 연결되어 있음을 1로 표시한다.

	1	2	3	4
0	0	0	0	0
1	0	1	1	1
2	1	0	1	1
3	1	0	0	1
4	1	1	1	0

즉, 1번 노드가 2번 노드와 연결되어 있으므로 1로 처리한다. 양방향 그래프의 경우 2번노드도 1번노드와 연결되어 있으니깐 1로 처리한다. (방향에 있을시에는 따로 고려해야한다.)

인접행렬은 구현이 쉽다는 장점이 있습니다.(내 입장에서는 인접행렬이나 인접리스트나 똑같다.)

하지만 인접행렬로 구현할 때의 치명적인 단점이 존재한다.

그것은 이 꼭지점의 갯수가 적을때만 가능하다는 점입니다. 그래프는 대부분 시작점에서 도착점을 찾는 방식의 탐색을 많이 하는데(예를 들어서 1번 지점에서 K번지점으로 무엇이 연결되있는지) 그럴려면 A[1][0~K]를 모든 개수를 탐색해야하는데, 그 개수는 v가 많아지면 v가 많아질수록 그만큼 탐색 시간이 오래걸리게 되고 매번 연결지점을 찾으려면 v크기만큼 돌아야되기 때문에 시간초과에 걸릴 확률이 정말정말 높습니다. 대부분 난이도가 높은 문제들은 v가 20000이 넘어서 만약 1->3 -> 20000 -> 2처럼 각 꼭지점에서 이 간선이 연결되어있는지 확인을 하려면 그만큼의 시간이 걸린다는 점입니다. 2만씩 5번만 반복해도 10만일텐데 대부분의 문제는 최소 100번은 반복해야될지도 모르고, 더 클 수도 있어서 유의해야합니다.

즉, 이 인접행렬의 경우는 꼭짓점(vertex)가 적은 경우에만 사용하는 것으로 합니다.

4.2 인접리스트로 구현

인접행렬은 2차원 배열을 통해서 표현 가능한 모든 노드에 대해서 연결되어 있는지(갈 수 있는지) 1 또는 0 으로 표현했다면, 인접리스트는 해당 노드에 대해서 연결되어 있는 노드의 정보만을 가지고 있다.

인접리스트는 연결되어 있는 노드에 대한 정보만을 가지고 있기 때문에, 인접행렬보다 메모리 절약이 되고 시간복잡도도 줄어든다.

해당 노드로부터 내가 갈 수 있는 노드에 대한 정보를 얻기 위해서는 인접행렬처럼 모든 노드의 개수를 순회하면서 확인하는 것이 아닌, 인접리스트는 애초에 내가 연결되어 있는 노드만을 저장하고 있기 때문에 내가 가지고 있는 노드들을 순회하기만 하면 된다.

인접리스트의 단점은 A노드와 B노드가 연결되있는지를 알고 싶은 경우에는 인접리스트는 A에는 B가 있는지 B에는 A가 있는지를 파악해서 연결되있는 걸 확인해야하기때문에 직접 다 뒤적거려야하는 단점이 생깁니다. (인접행렬의 경우 2차원 배열에서 인덱스값으로 바로 조회 가능)

제 개인적인 생각은 노드를 단지 방문했는지 안했는지의 여부파악이 목적이면 인접리스트가, 문제에서 두 노드간의 연결이 되어있는지의 파악을 많이 고려해야한다면 2차원배열이 낫다고 생각한다.

인접리스트로 구현할 때 주의할점은, 방문할 수 있는 노드가 여러개일 때 숫자가 작은 것 부터 방분 해야하는 경우는 알고리즘 수행 전에 리스트를 정렬을 수행해야 한다!!!!

5. 소스코드

5.1 인접행렬을 이용한 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int m;
	static int v;
	static int[][] graph;
	static boolean[] visited;
	
	static Queue<Integer> q;
	
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		v = Integer.parseInt(st.nextToken());
		
		graph = new int[n+1][n+1];
		visited = new boolean[n+1];
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			graph[x][y] = 1;
			graph[y][x] = 1;
		}
		
		// dfs 함수 호출
		dfs(v);
		
		System.out.println();
		Arrays.fill(visited, false);
		
		// bfs 함수 호출
		bfs(v);
	}
	
	static public void dfs(int start)   {
		visited[start] = true;
		
		System.out.print(start + " ");
		
		for(int i=0; i<n+1; i++) {
			if(graph[start][i] == 1 && visited[i] == false)
				dfs(i);
		}
	}
	
	static public void bfs(int start) {
		q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			
			System.out.print(temp + " ");
			
			for(int i=0; i<n+1; i++) {
				if(graph[temp][i] == 1 && visited[i] == false) {
					q.offer(i);
					visited[i] = true;
				}
				
			}
			
		}
	}
	
}

5.2 인접리스트를 이용한 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main2 {

	static int n;
	static int m;
	static int start;

	static List<List<Integer>> graph;

	static boolean[] visited = new boolean[n + 1];
	static Queue<Integer> q;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(st.nextToken());

		graph = new ArrayList<>();
		visited = new boolean[n + 1];
		Arrays.fill(visited, false);

		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			graph.get(x).add(y);
			graph.get(y).add(x);
		}

		// 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 위해 정렬수행
		for(int i=0; i<n+1; i++) {
			Collections.sort(graph.get(i));
		}
		
		// dfs함수 실행 args: start;
		dfs(start);

		System.out.println();
		Arrays.fill(visited, false);
		// bfs함수 실행 args: start;
		bfs(start);

	}

	static public void dfs(int start) {
		visited[start] = true;
		System.out.print(start + " ");
		
		for(int i:graph.get(start)) { 
			 if(visited[i] == false) 
				 dfs(i); 
		}
	
	}

	static public void bfs(int start) {
		q = new LinkedList<>();

		q.offer(start);
		visited[start] = true;

		while (!q.isEmpty()) {
			int temp = q.poll();
			System.out.print(temp + " ");

			for (int i : graph.get(temp)) {
				if (visited[i] == false) {
					q.offer(i);
					visited[i] = true;
				}
			}

		}

	}

}

'Coding Test > Algorithms' 카테고리의 다른 글

[Java] 덱 직접 구현하기 & 라이브러리 사용 JAVA (0)	2021.11.15
[Java] 큐 직접 구현하기 & 라이브러리 사용 JAVA (0)	2021.11.15
[Java] 스택 직접 구현하기 & 라이브러리 사용 JAVA (0)	2021.11.15
[Java] 브루트포스(순열과 조합 구현) JAVA (0)	2021.11.13
[Java] 정렬 알고리즘(Sort Algorithm) (0)	2021.08.17