자바 알고리즘 - 큐(Queue), BFS(너비 우선 탐색), 최단 횟수 찾기

이번에는 BFS 깊이우선탐색에 대한 글입니다. 역시나 DFS 와 마찬가지로 어마무시하게 중요합니다ㅠㅠ

 

- What is Queue?

큐(Queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First in First Out) 구조로 저장하는 형식이다. 스택(Stack)이 먼저 집어 넣은 데이터가 가장 나중에 나오는 자료 구조라면, 큐(Queue)는 먼저 들어간 데이터가 가장 먼저 나오는 구조이다.

아주 간단히 이야기하면 평소 우리가 놀이동산에서 놀이기구를 탈 때를 떠올리면 될 것 같다. 놀이동산에서는 먼저 줄을 선 사람이 먼저 놀이기구를 타게 된다. Queue 는 딱 이런 구조로 먼저 들어온 데이터가 가장 먼저 출력, 처리되는 형식이다.

 

1. BFS 는 넓이 우선 탐색

• BFS 는 Queue! DFS는 stack!
• DFS는 가장 깊은 레벨의 노드를 먼저 확인하는 방식이었다면 BFS는 같은 레벨에 있는 노드들을 먼저 탐색하고 그 다음 레벨 노드를 탐색하고 하는 방식
  • EX) 1 레벨 노드 모두 탐색, 2 레벨 노드 모두 탐색
• 얘는 보통 특정 노드에서 다른 노드까지의 최단값을 찾을때 사용됨
  • 서울에서 부산까지 가장 빠르게 갈 수 있는 방법은?
  • 최소로 걸리는 방법은 ~~? 대충 이런거는 거의 모두 BFS
• 이번에도 기본 트리는 아래 그림을 참고!!

기본 트리!

• BFS 의 탐색방법은 1 -> 2 -> 3-> 4 -> 5 -> 6-> 7 입니다. 즉 한 레벨의 노드를 모두 검사하고 다음 레벨의 노드로 넘어가고...이런 탐색을 계속한다.

 

• 다음은 코드입니다!! BFS 는 스택이 아닌 Queue 구조를 활용합니다. 이에따라서 코드가 DFS 랑은 살짝 차이가 있다
• 사실 순서는 간단하다
  • 현재 레벨에 있는 root Node 를 Q.offer 에 모두 넣어서 Q.size 즉 Queue 의 길이를 계산한다. 다음으로 len 길이의 끝까지 돌면서 자식노드(lt 와 rt) 가 있으면 다시 해당 노드를 Queue 에 넣에 넣는다. 한 레벨의 Q가 끝나면 Queue에 남아있는 다음 값들이 돌기 시작한다. 또한 한번 len 까지 돌리는 게 끝나면 Level 값을 1 증가시킨다.
  • 끝나는 때는 Queue 의 사이즈가 0 일 때 즉, Q.isEmpty() = true 일 때 종료하게 된다.

import java.util.LinkedList; // import 필수
import java.util.Queue; // import 필수

public class Algo_5_BFS {
	Node root;
	public void BFS(Node root) {
		Queue<Node> Q =  new LinkedList<>();
		Q.offer(root); // Queue 에 root 노드 넣기
//		Q.add(root) 도 가능
		
		int L = 0; // root 노드의 레벨값은 0
        
		while(!Q.isEmpty()) { // Queue 가 비어있지 않으면 while 문 진행
			int len = Q.size();	// Q 의 사이즈 구하기, 즉 해당 레벨의 노드 갯수
			System.out.println("Level = "+L);
			
			for(int i=0; i<len; i++) { // 해당 레벨의 사이즈가 len 이기 때문에 해당 레벨을 모두 출력하기 위한 for문
				Node cur = Q.poll(); // 가장 앞쪽 Queue 가져오기
				System.out.println("cur = "+cur.data+" ");
				
				if(cur.lt!=null) { // 현재 노드의 자식 노드 중 왼쪽 노드 값이 비어있지 않으면 Queue에 해당 왼쪽노드 넣기
					Q.offer(cur.lt);
				}
				if(cur.rt!=null) { // 현재 노드의 자식 노드 중 오른쪽 노드 값이 비어있지 않으면 Queue에 해당 오른쪽노드 넣기
					Q.offer(cur.rt);
				}
			} // for문 끝
			L++; // for문이 끝났다는 의미는 해당 레벨에서 알 수 있는 모든 노드에 대한 탐색이 끝났다는 의미임으로 다음 레벨은 L++
			// 이때 L 값은 root 노드로부터 거리라고 생각해도 좋다. 즉 시작점(root)부터 6 까지의 거리는 L값인 2 이다.
		}
		
	}
	
	public static void main(String[] args) {
		Algo_5_BFS tree = new Algo_5_BFS();
		
		tree.root = new Node(1); // root 노드 - 메모리값 100
		
		tree.root.lt = new Node(2); // 2 노드 - 메모리값 200
		tree.root.rt = new Node(3);
		
		tree.root.lt.lt = new Node(4);
		tree.root.lt.rt = new Node(5);

		tree.root.rt.lt = new Node(6);
		tree.root.rt.rt = new Node(7);
		
		tree.BFS(tree.root);
	}

}

출력은 아래처럼 된다!

순서대로 잘 돌습니다!

이거는 음...직접 코드를 쓰고, 출력을 해보면서 이해하는게 빠를듯하다ㅠㅠㅠ 설명하기 너무 어려워요ㅠㅠ

 

2. BFS 활용한 최단 거리 계산

• 문제 : 시작 좌표 s 와 목표 위치 e 가 주어진다. 이때 s 는 -1, +1, +5 셋 중 하나 밖에 행동하지 못한다. s 가 e 까지 갈때 최소 횟수로 도착하는 방법은?
• 이러한 화나는 문제가 있다면, 그때는 바로 BFS 를 활용해야 할 시간이다. => 최단거리, 최소 방법은 사실상 BFS 로 풀면 쉬워진다
• s = 5, e = 14 일 때 최단 횟수를 구한다고 해보자. 이 상태에서 트리를 그려보면 아래처럼 그려질 것이다.
  • 일단은 배열 부분이나 X 표시된 부분은 생각하지말고 그림 자체만 봐주시길 바랍니다.

다음으로 이를 바탕으로 코드를 작성해보았다. 역시나 코드 주석문을 참고하는게 이해에 도움이 되리라 생각한다.

• 먼저 우리에게 중요한 것은 이미 한번 갔던 좌표가 e 가 아닌 이상 더이상 갈 필요가 없다는 점이다(출력 시간 단추을 위해) 이를 위해서 ch 배열을 사용하는데 이미 한번 갔던 좌표가 5라면 배열의 인덱스 5번에 1 값을 넣어서 코드가 돌면서 이미 1 값이 넣어진 곳은 더이상 가지 않도록 하기 위함이다. => 위 트리에서 빨간색 X 표시 된 곳이 이미 방문하였던 값들이다.
• dis 배열은 내가 행동할 수 있는 행위들을 넣어놓은 배열이다.
• 다시 돌아욧 이 한번 출력될때마다 L+1 한다고 생각하면 된다. 이는 한 레벨의 탐색이 모두 끝나고 그 다음 레벨의 Node를 탐색하는것이기 때문이다.
• Queue 매서드 활용은 아래 표에 한번 더 정리해두었다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// s 부터 e 까지 최단으로 가는 방법

public class Algo_6_BFS {
	Node root;
	
	int answer = 0; // 최단거리 계산, Level 값과 동일
	int[] dis = { -1, 1, 5}; // 각 숫자 사용 여부, 사용하면 해당 배열의 위치에 1 입력됨, 사용안하면 0
	int[] ch; 
	// ch 배열은 아래와 같은 역할을 함
	// 1. 시작하는 좌표값을 저장해두기 위해서
	// 2. Queue 에 한번 계산된 숫자는 다시 계산하지 않게 하기 위해 사용하는 배열
	
	Queue<Integer> Q = new LinkedList<>();
	
	public void BFS(int s, int e) { // s 와 e 가 주어짐
		ch = new int[10001]; // 좌표가 1 ~ 10000까지
		
		ch[s] = 1; // ch 배열은 10000 까지 있는데 한번 계산한 곳은 1을 넣어서 중복계산이 없도록 함
		Q.offer(s); // Queue 에 시작값을 넣음
		int L = 0;
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			
			for(int i=0; i<len; i++) {
				int x = Q.poll(); // 현재 노드를 꺼내옴
				System.out.println("현재 위치 : "+x);
				
				for(int k = 0; k<3; k++) {
					int nx = x+dis[k]; 
					// 현재 좌표(노드)에서 다음 자식 노드값을 더함
					// 이때 더해지는 값은 dis 배열의 값, -1, +1, +5
//					System.out.println(nx);
					
					if(x == e) {
						System.out.println();
						System.out.println("목표 위치 탐색 완료");
						System.out.println("최단 횟수 : "+L);
						
						System.out.println();
	
						// 한번 탐색된 값 찍기 : 확실하지 않을 수 있습니다ㅠ
						for(int u=0; u<ch.length; u++) { 
							if(ch[u]==1) {
								System.out.print(u+" ");
							}
						}
						return;
						// 만약 int BFS 라면 return L; 해주어야함
					}
					
					if(1 <= nx && nx <= 10000 && ch[nx] == 0) {
						// ch[nx] == 0 의 의미는 이미 한번 계산한 좌표는 ch[nx] == 1 이 되기 때문에
						ch[nx] = 1;
						Q.offer(nx);

					}
				}
			}
			L++;
			System.out.println();
			System.out.println("다시 돌아욧");
			System.out.println();
		}
		
		// return 0; int 형식이면 때문에 return 구문을 마지막에 한번 더 넣어줘야함
	}
	
	public static void main(String[] args) {
		Algo_6_BFS algo = new Algo_6_BFS();
		
		Scanner scan = new Scanner(System.in);
		int s = scan.nextInt();
		int e = scan.nextInt();
		
		System.out.println("시작 값 : "+s);
		System.out.println("목표 위치 : "+e);
		System.out.println();
		
		algo.BFS(s, e);
		

	}

}

 

출력은 아래 처럼!!

s = 5, e = 14 일 때

※ Queue 활용하기

1. 선언방법

import java.util.LinkedList; //import 필수
import java.util.Queue; //import 필수

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언시 사용됨, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언시 사용됨, linkedlist 이용

Queue 는 LinkedList 를 사용하기때문에 Queue 와 LinkList 모두 import 되어있어야한다.

 

2. 사용 할 수 있는 메서드

메서드	사용법
Queue.add(Value) or Queue.offer(Value)	Queue 에 vlaue 를 삽입	삽입 성공시 ture, 삽입에 실패하면 IllegalStateException
queue.poll()	현재 queue의 첫 번째값을 반환&삭제
queue.remove()	현재 queue의 첫 번째값을 삭제
queue.clear()	queue 초기화
queue.size()	현재 queue 의 size 즉 길이 반환