이번 포스트에서는 자바의 알고리즘 중 그래프에 대해서 그것이 뭔지 어떻게 구현을 할 수 있는지에 대해서 공부하고 정리를 해보겠습니다!
Graph
Graph라는 것은 vertex(정점)와 edge(간선)로 구성된 한정된 자료구조를 의미합니다.
이렇게 다양한 방식으로 그래프를 표현할 수 있습니다. 하지만, 여기서 위의 사진을 보고 트리 구조와 유사하다는 것을 알 수 있습니다.
그래프와 트리의 비교
| 그래프 | 트리 | |
|---|---|---|
| 정의 | 노드와 간선을 하나로 모아 놓은 자료구조 | 그래프의 한 종류(방향성이 있는 비순환 그래프) |
| 방향성 | 방향 그래프, 무방향 그래프 | 방향 그래프 |
| 사이클 | Cyclic 순환 그래프, Acyclic 그래프 모두 가능 | Acyclic 그래프 |
| 루트 노드 | 루트 노드의 개념이 없다. | 가장 위에 루트 노드가 존재합니다. |
| 부모 자식 | 부모-자식의 개념이 없다. | 부모-자식 관계로 이뤄져 모든 자식 노드는 한개의 부모 노드만을 가집니다. |
| 모델 | 네트워크 모델 | 계층 모델 |
| 순회 | DFS, BFS | Pre-order, In-order, Post-order/ Level-order |
| 간선의 수 | 그래프 마다 다르다. | 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. |
| 경로 | 2개 이상의 경로가 가능하다. | 양 노드 간의 경로는 1개만 가질 수 있다. |
무방향 그래프(Undirected Graph)
- 두 정점을 연결하는 간선에 방향이 없는 그래프로 표현을 함에 있어 양 방향 그래프라고도 생각할 수 있습니다.
- (a, b) = (b, a)
방향 그래프(Directed Graph)
- 두 vertext를 연결하는 edge에 방향이 있는 그래프입니다. 방향이 존재하기 때문에 지정된 방향으로만 이동이 가능합니다.
- (a, b) ≠ (b, a)
가중치 그래프(Weight Graph)
- vertex를 연결하는 edge에 weight를 할당한 그래프입니다.
이제는 어떤 방법으로 그래프를 탐색할 수 있는지를 알아보겠습니다.
DFS&BFS
static void dfs(int startPoint, int graphPoint){
// 일부러 해당 위치의 값을 맞게 수정하기 위함이다.
visited = new boolean[graphPoint];
dfsRecur(startPoint, visited);
}
static void dfsRecur(int startPoint, boolean[] visited){
visited[startPoint-1] = true;
System.out.print(startPoint + " ");
List<Integer> childNode = arr.get(startPoint-1);
int cnt = 0;
while(!childNode.isEmpty() && cnt <= childNode.size()-1){
// 처음의 요소를 가져온다.
int crnt = childNode.get(cnt);
if(!visited[crnt-1]){
dfsRecur(crnt, visited);
}else{
cnt++;
}
}
}
static void bfs(int startPoint, int graphPoint){
// dfs 이후 visited 새로운 객체를 생성해 초기화
visited = new boolean[graphPoint];
bfsRecur(startPoint, visited);
}
static void bfsRecur(int startPoint, boolean[] visited){
Queue<Integer> que = new LinkedList<>();
que.offer(startPoint);
visited[startPoint-1] = true;
// List<Integer> childNode = arr.get(startPoint-1);
while(!que.isEmpty()){
int crnt = que.poll();
System.out.print(crnt + " ");
for(int i = 0; i < arr.get(crnt-1).size(); i ++ ){
int next = arr.get(crnt-1).get(i);
if (!visited[next-1]) {
que.add(next);
visited[next-1] = true;
}
}
}
}DFS와 BFS는 모두 그래프의 모든 노드를 방문하는 완전 탐색 방식입니다. 하지만 요소를 탐색하는 방식에서 차이가 발생합니다.
- DFS는 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동하는 방식입니다. DFS는 경로의 특징을 저장해야하는 문제에 대해서 사용합니다.
주로 스택이나 재귀함수로 구현을 하고, 이렇게 먼저 끝까지 먼저 탐색을 진행하는 특징에 의해서 모든 노드를 방문하고자 하는 경우에는 이 방법을 선택하게 됩니다.
- BFS는 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동하는 방식입니다. BFS는 최단거리를 구하거나, 모든 정점을 방문하여 탐색을 해야하는 경우에 사용합니다.
주로, 큐를 통해서 구현하고 시작점을 주게 되어 해당 노드를 시작으로 인접한 노드를 먼저 탐색하는 방법으로 시작 vertex로부터 가까운 vertex를 먼저 방문하고 멀리 떨어져 있는 vertex를 나중에 방문하는 순회 방법입니다.
💡 Time Complexity
이렇게 구현한 DFS와 BFS는 인접 리스트와 인접 행렬을 통해서 코드를 구성할 수 있습니다. 이때 각각의 구현 방식에 대한 시간 복잡도는 아래와 같습니다.
- 인접 리스트 : O(N+E), 인접 리스트의 경우는 해당 노드에 연결된 노드에 대한 정보만 저장되어 있기 때문에 중첩 반복문을 필요로 하기 않습니다.
- 인접 행렬 : O(N^2), 인접 행렬의 경우는 탐색에 있어 이중 반복문을 돌려야 하기 때문에 반드시 해당 시간 복잡도가 소요가 됩니다.
- 응용 문제! (안전 지대)
일단 해당 문제에 대한 해설을 진행하겠습니다.
배열에 대한 정보가 주어지면, 그 각 요소가 산이라고 생각할 수 있습니다.
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7이때, 비가 랜덤으로 온다고 가정을 했을때 안전지대의 개수를 찾아야하는 문제입니다.
여기서 중요한것은 비는 안올 수도 있다는 점입니다. 그렇기 때문에 강수량에 대한 반복문을 0부터 시작하여 배열에 나온 최댓값까지 실행을 해줍니다. 여기서 Math.max 메서드를 사용하여 최댓값에 대한 정보를 가져옵니다.
arr = new int[square][square];
int max = 0, max2 = 0;
for(int i = 0; i < square; i++){
for(int j = 0; j < square; j++){
int a = sc.nextInt();
arr[i][j] = a;
max = Math.max(max, a);
}
}
for(int i = 0; i <= max; i++){
max2 = Math.max(max2, dfs(i));
}숫자가 증가함에 따라서 dfs라는 함수안의 매개변수가 달라지기 때문에 이를 인식을 하고 침수 여부와 방문 여부를 확인하기 위한 배열을 초기화 해줘야합니다.
static int dfs(int startPoint){
int cnt = 0;
flood = new boolean[square][square];
visited = new boolean[square][square];
for(int i = 0; i < arr.length; i ++){
for(int j = 0; j < arr.length; j++){
if(!flood[i][j] && arr[i][j] > startPoint && !visited[i][j]){
dfsRecur(startPoint,i,j);
cnt++;
}
}
}
return cnt;
}이중 반복문 안의 조건문을 보면 방문 처리와 침수된것에 따라 cnt를 증가 시켜줍니다. 여기서 처음 변수에 대해서는 무조건 작동하기 때문에 cnt는 1부터 시작한다고 할 수 있습니다.
추후의 함수는 재귀적으로 호출하게 만들었습니다.
static void dfsRecur(int startPoint, int x, int y){
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{x,y});
visited[x][y] = true;
if(arr[x][y] <= startPoint){
flood[x][y] = true; // true일 경우에 물에 잠김으로 표시를 하자
}
while(!stack.isEmpty()){
int[] z = stack.pop();
int nX = z[0];
int nY = z[1];
for(int i = 0; i < 4; i++){
int mX = nX + move[i][0];
int mY = nY + move[i][1];
if(mX < 0 || mX > arr.length-1 || mY < 0 || mY > arr.length-1){
continue;
}
if(!flood[mX][mY] && arr[mX][mY] > startPoint && !visited[mX][mY]){
stack.push(new int[]{mX, mY});
visited[mX][mY] = true;
}else{
flood[mX][mY] = true;
visited[mX][mY] = true;
}
}
}
}이제 다익스트라, 벨맨 포드 알고리즘, 위상 정렬, 유니온 파인드, 플로이드-워셀, 최소 신장 트리 알고리즘에 대해서 공부한 것을 적어보겠습니다.
Union Find
추후에 나올 알고리즘들 중에서 가장 기초라고 할 수 있는 유니온 파인드에 대해서 알아보겠습니다. 해당 알고리즘은 처음 접하는 사람들에게는 하나의 고유 명사처럼 느껴 질 수 도 있으나 해당 개념은 Union과 Find의 합성어로써, 집합을 만들기 위해서 일단 Find 검색하고 결합하는 일련의 과정을 말합니다.
직접적인 코드 예제를 통해서 조금 더 공부해보겠습니다
package baekjoon;
import java.io.*;
import java.util.*;
public class friendMain {
static int[] parents;
static int[] level;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int friends = Integer.parseInt(br.readLine());
while(friends != 0){
int listAmount = Integer.parseInt(br.readLine());
// 집합의 갯수에 따른 입력의 값이 2개씩 들어오기 때문에 집합의 총 개수 * friends하여 배열을 선언한다.
parents = new int[listAmount*2];
level = new int[listAmount*2];
// 선언한 배열 초기화
for (int i = 0; i<parents.length;i++) {
parents[i] = i;
level[i] = 1;
}
// 중복 제거 및 집합의 간략화를 위한 HashMap 함수 차용
Map<String, Integer> map = new HashMap<>();
int ind = 0;
for(int i = 0; i < listAmount; i++){
st = new StringTokenizer(br.readLine(), " ");
String name1 = st.nextToken();
String name2 = st.nextToken();
// 조건문을 사용해 이미 포함된 key는 따로 추가하지 않는다.
if (!map.containsKey(name1)) {
map.put(name1, ind++);
}
if (!map.containsKey(name2)) {
map.put(name2, ind++);
}
// union(map.get(name1), map.get(name2))를 집합을 정맇하는 반복문 안에 넣어서 논리적인 연결 관계를 계속 형성하고 level에 대한 값을 바꾸고 출력한다.
bw.write(union(map.get(name1), map.get(name2)) + "\n");
}
friends--;
}
bw.close();
br.close();
}
static int union(int x, int y){
x = find(x);
y = find(y);
if(x != y){
parents[y] = x;
level[x] += level[y];
level[y] = 1;
}
return level[x];
}
static int find(int z) {
if (parents[z] == z)
return z;
else
return parents[z] = find(parents[z]);
}
}
해당 코드는 백준의 4195번에 대한 문제입니다. 해당 문제에 대한 입력은
2 // 전체 반복 횟수
3 // 집합의 갯수
Fred Barney // 순서대로 친구가 된 사람들의 이름
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty위의 입력에 주석으로 달아 놓은 것 처럼 입력이 들어오게 됩니다. 그러면 해당 입력을 가시화를 해보겠습니다.
위의 그림처럼 입력한 데이터에 대하여 index를 만들어 중복을 제거하기 위한 HashMap에 넣고 그 해당 데이터를 각각 다시 꺼내 Union 함수로 보내어 헤더의 값이 같은지 확인 합니다.
static int union(int x, int y){
x = find(x);
y = find(y);
if(x != y){
parents[y] = x;
level[x] += level[y];
level[y] = 1;
}
return level[x];
}여기서 header의 값은 find라는 함수로 찾게 됩니다. 기본적으로따로 설정하지 않는 이상은 논리적으로 연결되지 않은 노드들에 대해서는 header가 자기자신을 가르키게 됩니다.
static int find(int z) {
if (parents[z] == z)
return z;
else
return parents[z] = find(parents[z]);
}만약 헤더 값이 같은 경우, 즉 논리적으로 연결되어 있는 경우에는 정말 서로 논리적으로 연결되어 있는지를 확인하기 위해서 재귀적으로 계속적으로 올라가 header 값을 확인하고 return을 하게 됩니다. 이렇게 find 값을 return을 하게 되면 그에 따라 level에 원래 1이라는 변수를 전부 저장해 놓았던 것에 논리적인 연결이 쌓일 수 록 +1을 해줍니다. 그렇게 되면 각 논리적인 연결에 따른 길이를 알수 있고 추후에 연결되는 것들에 대해서도 길이를 합쳐 구할 수 있습니다.
References
1. Graph Definition
2. DFS/BFS
