양술사의 쉬운 IT

BFS는 너비 우선 검색이고, 가까운 레벨/가까운 노드를 먼저 검색하는 방식으로 수행되는 알고리즘이다. 최종 목표는 모든 노드(정점)을 탐색하는 것이다.

큐(Queue)를 사용하고, DFS 대비 최단 거리/비용을 계산하는데 효율적인 알고리즘이다.

그림으로 BFS를 이해하기

아래의 그래프를 통해서 BFS의 매커니즘을 이해해본다.

크게 8개의 정점, 9개의 간선, 오른쪽에는 큐(Queue)가 있다.

1. 1번 노드를 먼저 검색한다. 1번 노드를 큐에 담고, 내가 해당 노드를 탐색했다는 것을 의미하는 "방문처리"를 해야 한다. 방문 처리는 그림 상에서 파란색으로 표기했다.

큐(Queue)는 FIFO(First In First Out) 특성을 지닌 자료구조로, 먼저 들어간 것이 먼저 밖으로 나온다. 

2. 큐에서 한개를 꺼내고, 연결된 노드들을 큐에 모두 넣는다.

즉, 큐에 있는 1번 노드를 꺼내서 출력하고, 1번과 연결된 2,3 노드를 큐에 담는다. 마지막으로 큐에 넣은 노드를 내가 검색하고 탐색한 노드이니까, 방문 처리(파란노드로 변경) 한다.

3. 큐에서 한개를 꺼내고 연결된 노드들을 큐에 모두 넣는다.

2번 노드를 꺼내고, 2번 노드와 연결된 노드인 6,8 노드를 큐에 담는다. 그리고 6,8은 내가 확인한 노드이니, 역시나 방문처리를 한다.

4. 마찬가지로 큐에서 3번 노드를 꺼내고, 연결된 노드인 5번 노드를 큐에 넣는다. 꺼낸 노드는 출력한다.

5. 큐에서 6번 노드를 꺼내고, 6번 노드와 연결된 노드가 없으므로 다시 큐에서 하나의 노드를 꺼낸다.

다음으로 꺼낼 노드는 8번이고, 8번 노드와 연결된 노드는 이미 방문처리된 것들 뿐이므로, 다시 큐에서 노드를 꺼낸다.

6. 큐에서 5번 노드를 꺼내고, 5번 노드와 연결된 4,7번 노드를 큐에 담는다. 큐에 담은 4,7번 노드는 방문 처리하고, 꺼낸 5번 노드는 출력한다.

7. 큐에서 노드 하나를 꺼내고, 방문하지 않은 노드를 찾아서 큐에 담는다.

즉, 4번 노드를 꺼내지면, 4번 노드와 연결된 노드 중에서 방문하지 않은 노드는 없으므로, 출력만 한다.

다시 7번 노드를 꺼내고 방문하지 않는 노드를 찾지만 없으므로, 출력하고 끝낸다.

최종적으로 1, 2, 3, 6, 8, 5, 4, 7 순으로 방문한다는 결론에 이른다. 

(여기서는 오름차순 기준으로 큐에 넣는다는 가정으로 설명하였으며, 실제 내부적인 기준에 따라서 결과는 일부 달라질 수 있다.)

JAVA로 구현한 BFS 사례

import java.util.LinkedList;
import java.util.Queue;

public class bfs_queue {

	// 방문처리를 위한 boolean 배열 선언
	static boolean[] visited = new boolean[9];
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		bfs(1);
	}
	
	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		
		// 큐에 BFS를 시작할 노드번호 담기
		q.offer(start);
		
		// 큐에 넣은 노드를 방문처리
		visited[start] = true;
		
		// 큐가 비어있을 때까지 반복수행
		while(!q.isEmpty()) {
			int node_out = q.poll(); // 큐에서 1개 노드 꺼내기
			
			System.out.print(node_out + "->"); // 꺼낸 노드 출력
			
			for(int i=0 ; i < graph[node_out].length ; i++) {
				int temp = graph[node_out][i];
				
				// 방문하지 않은 경우만 if 문 수행
				if(!visited[temp]) {      // 방문하지 않은 노드라면
					visited[temp] = true; // 방문 처리한 후에
					q.offer(temp);        // 큐에 넣는다.
				}
			}
		}
	}

}

출력된 결과는 다음과 같다.

1->2->3->8->6->5->4->7->

1. 기본 For  구문

예전부터 사용되던 For 문 형태로 for(초기화 ; 조건문 ; 증감) 으로 구성한다.

for(int i=0 ; i < parent.length++) {
	...
}

i가 0부터 parent.length 값 만큼 반복적으로 수행된다. parent.length가 100이라면, 0부터 100까지 i 값이 1씩 증가하면서 수행된다. 즉 i가 0부터 99까지 100번을 수해앟ㄴ다.

2. 응용 For 문

for(출력할 변수정의 : 배열) 형식으로 작성하고, 가운데 기호는 :(콜론) 이다.

int arr[] = {"a","b","c","d","e"};
for(String i : arr){
	System.out.println(i);
}

arr의 배열을 처음부터 하나씩 실행해서 i에 할당해주면, 출력한다. 즉, arr 배열의 처음부터 끝까지 하나씩 반복해서 출력하는 것이다.

단, for : 구문은 배열 자료구조만 활용가능하며, 배열의 값은 변경할 수 없다.

1차원 배열의 오름차순

import java.util.Arrays;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};

		Arrays.sort(arr,(o1,o2)->Integer.compare(o1[0], o2[0])); // ◀◀◀
		
		for(int i=0 ; i<arr.length ; i++)
			System.out.println(arr[i][0] + " " + arr[i][1]);
	}
}

또는

import java.util.Arrays;

public class array_sort {

	public static void main(String[] args) {
		int arr[] = {3,75,98,2,21,11,94};
		Arrays.sort(arr);

		for (int i : arr)
			System.out.print(i + " ");
	}

}

출력 결과는 다음과 같다.

2 3 11 21 75 94 98

1차원 배열의 내림차순

import java.util.Arrays;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};

		Arrays.sort(arr,(o1,o2)->Integer.compare(o2[0], o1[0])); // ◀◀◀
		
		for(int i=0 ; i<arr.length ; i++)
			System.out.println(arr[i][0] + " " + arr[i][1]);
	}
}

또는

import java.util.Arrays;
import java.util.Collections;

public class array_sort {

	public static void main(String[] args) {
		Integer arr[] = {3,75,98,2,21,11,94};
		Arrays.sort(arr, Collections.reverseOrder());

		for (int i : arr)
			System.out.print(i + " ");
	}
}

출력 결과는 다음과 같다.

98 94 75 21 11 3 2

2차원 배열의 오름차순

• 1열 기준으로 오름차순 정렬

import java.util.Arrays;
import java.util.Comparator;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};
		
		Arrays.sort(arr, new Comparator<int[]>(){
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
				
		})	;
		
		for (int i=0; i < arr.length ; i++)
			System.out.println(arr[i][0]+" "+arr[i][1]);
	}
	

}

출력 결과는 다음과 같다.

1 5
1 4
4 3
4 2
8 6
10 7

• 2열 기준으로 오름차순 정렬

Comparator 함수 부분의 return 만 아래 부분으로 변경하면 된다.

return o1[1]-o2[1];

•  1열과 2열 모두 오름 차순 정렬

import java.util.Arrays;
import java.util.Comparator;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};
		
		Arrays.sort(arr, new Comparator<int[]>(){

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0]==o2[0])
	        			return o1[1]-o2[1];
				else
					return o1[0]-o2[0];
			}
			
		});		
		for(int i=0 ; i<arr.length ; i++)
			System.out.println(arr[i][0] + " " + arr[i][1]);
	}
}

출력결과는 다음과 같다.

1 4
1 5
4 2
4 3
8 6
10 7

2차원 배열의 내림차순

• 1열 기준으로 내림차순 렬

import java.util.Arrays;
import java.util.Comparator;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};
		
		Arrays.sort(arr, new Comparator<int[]>(){

			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[0]-o1[0];
			}
			
		});		
		for(int i=0 ; i<arr.length ; i++)
			System.out.println(arr[i][0] + " " + arr[i][1]);
	}
}

출력 결과는 다음과 같다.

10 7
8 6
4 3
4 2
1 5
1 4

• 2열 기준으로 내림차순 정렬

Comparator 함수 부분의 return 만 아래 부분으로 변경하면 된다.

return o2[1]-o1[1];

• 1열과 2열 기준으로 내림차순 정렬

import java.util.Arrays;
import java.util.Comparator;

public class array_sort {

	public static void main(String[] args) {
		int arr[][] = {{4,3},{8,6},{4,2},{10,7},{1,5},{1,4}};
		
		Arrays.sort(arr, new Comparator<int[]>(){

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]==o2[1])
					return o2[1]-o1[1];
				else
					return o2[0]-o1[0];
			}
			
		});		
		for(int i=0 ; i<arr.length ; i++)
			System.out.println(arr[i][0] + " " + arr[i][1]);
	}
}

출력 결과는 다음과 같다.

10 7
8 6
4 3
4 2
1 5
1 4

그래프 알고리즘 하위의 유니온 파인드(Union-Find) 알고리즘에 대해서 알아본다.

해당 알고리즘의 구성요소는 유니온(Union)과 파인드(Find)이다.

1. 개념

• 그래프 알고리즘
• "합집합 찾기" 라는 의미
• 서로소인 부분 집합 찾기
• 다수 노드 중에서 특정한 두 개가 서로 같은 그래프에 속하는지 판단하는 알고리즘
• union(x,y)와 find(x) 연산으로 구성됨
  • union(x,y) : x와 y 합치기. 즉, x와 y 노드의 각 부모를 합친다고 생각해야 한다.
    만약 union(3,4)라고 한다면, 3번 노드의 최상위 부모와 4번 노드의 최상위 부모를 합쳐야 하는 것이다.
  • find(x) : x가 어느 그래프에 속하는지 확인하기. 즉, x 노드의 부모들을 찾는 과정에서 부모가 없는 최상위 부모를 찾는 것이다.
    만약 find(4) 를 수행해본다고 가정한다. 그럼 4번 노드의 부모를 찾고, 3번 노드라는 사실을 확인한다. 다시 3번 노드의 부모를 찾으면 1번 노드이다. 그 다음으로 1번 노드의 부모를 찾으면 나 자신인 1번 노드가 부모 노드인 것이다. 따라서 1번 노드가 find(4)의 결과인 것이다.

2. 전제

• 다른 것과 연결되지 않은 노드는 혼자이다. 따라서 부모 노드(연결 노드)를 물어본다면, 나 자신이 된다.
• 유니온 파인드에서는 상대적으로 작은 숫자를 부모라고 선택한다. 1과 2를 합치기로 했다면, 1이 부모가 된다.
  3과 10을 합치기로 했다면, 3이 부모가 된다고 전제한다.

3. 유니온 파인드 예시

(1) 부모 노드 초기화

1번 ~ 5번 노드가 있다. 각 노드는 다른 노드들과 연결되지 않고, 자기 자신이 부모가 된다. 특정 노드 번호는 x라고 하면, x의 부모 노드를 확인하는 것은 parent(x) 로 수행할 수 있다.

(2) union(1,2)

1번 노드가 속한 그래프와 2번 노드가 속한 그래프를 합친다. 작은 숫자가 부모가 되므로, 2번 노드의 부모는 1번 노드가 된다. 수식으로 정리하면 parent(2) = 1 이 된다.

(3) union(3,4), union(3,5)

위와 같은 방식으로 parent(4)=3, parent(5)=3이 된다.

만약 2번 노드와 5번 노드의 부모를 찾으려면 find로 찾을 수 있다.
find(2) = 1, find(5) = 3이 된다.

(4) union(2,4)

2번 노드가 속한 그래프와 4번 노드가 속한 그래프를 합쳐야 한다. 즉, 2번 노드의 최상위 노드와 4번 노드의 최상위 노드를 합쳐야 하는 것이다. 각 노드의 최상위 노드는 아래와 같이 find 를 통해서 계산합니다.

• find(2) = 1
• find(4) = 3

결국 1번 노드와 3번 노드를 합치는 것이고 숫자가 작은 1번 노드가 부모 노드가 됩니다.

• find (4) = 1

4. Java로 구현한 유니온 파인드의 주요 함수

• Find 함수 : 특정 노드의 최상위 노드 리턴. 재귀 함수

public static int find(int x) {
   if(parent[x] == x) return x;
   else
      return parent[x] = find(parent[x]);
}

• Union 함수 : 특정 노드 2개가 속한 그래프를 합치는 함수로써, 최상위 노드를 찾아서 합쳐야 한다. 각 노드의 최상위 노드는 find()로 찾아서, 부모값을 재설정한다.

public static void union (int x, int y) { // x와 y를 합치기
   x = find(x); // x번 노드의 최상위 노드 구하기
   y = find(y); // y번 노드의 최상위 노드 구하기

   if(x <= y) // x,y번 노드의 최상위 노드가 다르면 다른 그래프이므로, 합쳐야 한다.
      parent[y] = x; // y번 노드의 부모노드를 x번 노드의 부모노드로 교체한다.
   else
      parent[x] = y;
}

• IsSameParent 함수 : 특정 노드 2개가 같은 그래프인지 판단하는 함수로, 각 노드의 최상위 노드가 같은지 여부를 판단할 필요가 있으면 사용한다.

public static int isSameParent (int x, int y) {
   x = find (x) ; 
   y = find (y) ; 
   
   if (x == y) return 1;
   
   return 0;
}

5. Java 코드로 구현한 유니온 파인드 전체

public class main(){

   public static void main(String[] args) {
      int N = 5;
      parent = new int[N];

       //부모노드 초기화
      for (int i = 0 ; i < parent.length ; i++)
         parent[i] = i++;

      union(1,2);
      union(3,4);
      union(3,5);
      union(2,4);  
   }

   // union 함수
   public static void union(int x, int y){
      x = find(x);
      y = find(y);

      if(x <= y)
         parent[y] = x;
      else
         parent[x] =y;
   }

   // find 함수
   public static int find(int x) {
      if(parent[x] == x) return x;
      
      return parent[x] = find(parent[x]);

   }
}

우리는 리눅스 계열의 서버에 접속하려는 경우에 SSH 프로토콜을 사용합니다. SSH를 통해 까만 커맨드 창에 접속하는 입구는 일반적으로 22 포트를 사용하구요.

여기서 포트(Port)는 마치 아파트의 호수와 비슷하다고 이해하시면 좋을 것 같습니다. 아파트 입구까지만 왔더라도, 정확한 호수를 알아야 원하는 장소에 도착하듯이, 서버를 접속하는 경우에도 서버의 IP 주소 뿐만 아니라, Port라는 구체적인 동/호수를 알아야 접속할 수 있습니다.

SSH 터널링 개념

아래는 우리가 Server A, Server B 접속하려는 계획을 보여주고 있습니다. Server A는 SSH 프로토콜인 22 포트를 통해서 서버에 접속하려고 하고, Server B는 80 포트를 통해서 기동된 애플리케이션을 사용하려는 것입니다.

나의 PC -- 22 → Server A 접속
나의 PC -- 80 → Server B 접속

그러나 나의 PC가 있는 공간은 조금의 제약이 있을 수도 있습니다. 만약 회사 사무실에서 Server A,B를 접속한다고 가정합시다. 회사 안이거나 학교 안에서 설정한 방화벽으로 인하여 Server B에 접속할 수 없는 상황이 있을 수 있습니다. 이런 경우에 Server B에 어떻게 접속할 수 있을까? 고민스러울 것이다.

위와 같은 경우에 우리는 바로 터널링(Tunneling) 기술을 활용하여 Server B를 접속할 수 있습니다. 바로 Server A를 거쳐서 Server B에 도착하는 것입니다. Server A에 접속한 후, Server B로 향하는 터널을 만든다고 생각하면 됩니다. 만든 터널을 통해서 Server A → Server B로 향하는 것입니다.

터널링은 포트 포워딩(Port Forwarding)이라는 용어로도 불립니다. 터널링 = 포트 포워딩!

나의 PC -- 22 → Server A → Server B

그럼 Command 측면에서는 SSH 터널링을 어떻게 할 수 있는지 알아보도록 합니다. ssh 프로토콜을 조금 더 편하게 사용하기 위해서 도구를 활용하기도 하지만, 근본적인 터널링이 어떤 명령어 기반으로 수행되는지를 먼저 이해하도록 합니다.

그 전에 각 서버에 대한 IP와 Port를 가정하도록 합니다.

• Server A : IP 주소는 192.168.0.1, 포트는 22번으로 접속
• Server B : IP 주소는 192.168.0.2, 포트는 80번으로 접속

SSH 접속 명령어

단순하게 Server A에만 접속하는 ssh 명령어를 짚고 넘어갑니다.

SSH 접속 명령어 : ssh [서버A 계정]@[서버IP주소] -p [접속할 포트]

$ ssh jey@192.168.0.1

로 입력할 수 있습니다. -p 22 를 제외한 이유는 ssh 명령어의 디폴트 포트가 22번이므로 따로 작성하지 않았습니다. 만약 ssh 포트가 22가 아닌 다른 값으로 사용한다면, -p 접속할포트를 작성해주어야 합니다.

SSH 터널링 명령어

그럼 본격적으로 내 PC에서 Server A를 거쳐서 Server B에 접속하는 방법을 알아봅니다.

SSH 터널링 명령어 : ssh -L [접속에 사용할 원하는 포트]:[최종 접속할 서버 IP]:[최종 접속할 서버 포트]  [거처갈 서버]

조금 쉽게 설명하면 최종 접속할 서버는 Server B이고 거쳐갈 서버는 Server A가 됩니다. 명령어도 문법과 유사하기 때문에, 해당되는 값으로 변경하면 됩니다. 즉, ssh -L [원하는포트]:[Server B IP]:[Server B Port]  [Server A IP] 으로 이해하면 됩니다.

$ ssh -L 1234:192.68.0.2:80 192.168.0.1

위의 터널링을 내 PC에서 수행하는 동시에, 내 PC → Server A → Server B로 바로 접속할 수 있는 통로가 생긴 것입니다. 비록 눈에 보이진 않지만요. Server B는 80포트로 접속해야 하므로, 웹 브라우저에서 Server B에 접속해봅니다.

웹 브라우저의 URL 입력창 : localhost:[이전에 정한 원하는 포트]

그럼 Server B의 기동된 애플리케이션을 확인할 수 있습니다.