큐를 이용한 BFS 코드 (자바)

가중치가 일정한 경우 최단거리를 구할 때 BFS를 이용한다.

두개의 코드는 큐를 이용한 것이고, 트리와 배열은 모두 코드에서 직접 선언 했다.

 

BFS를 이용한 트리 탐색

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

/* 큐를 이용한 BFS 트리 전체 탐색을 방문 순서대로 출력 (노드 번호, 깊이)
        1
     2      3
   4  5   6   7
      8   9
*/

public class StudyBFSTree {
        
        public static void main(String[] args) {
                // 그래프 생성
                
                ArrayList<Integer>[] G = new ArrayList[10];
                boolean[] isVisited = new boolean[10];
                
                for (int i = 1; i<= 9; i++) {
                        G[i] = new ArrayList<Integer>();
                }
                
                G[1].add(2);
                G[1].add(3);
                
                G[2].add(4);
                G[2].add(5);
                
                G[3].add(6);
                G[3].add(7);
                
                G[5].add(8);
                G[6].add(9);
                

                // 탐색 준비
                Queue<int[]> queue = new LinkedList<int[]>();        // 방문한 depth 까지 출력
                int now[] = new int[2];        // 0 : 노드 번호, 1 : 깊이
                
                
                now[0] = 1;                // 1에서 시작
                now[1] = 1;                // 깊이 1 (처음이니까)
                
                isVisited[now[0]] = true;
                queue.add(now);
                
                // 탐색 시작
                while (!queue.isEmpty()) {
                        now = queue.poll();
                        
                        System.out.println(Arrays.toString(now));
                        
                        for (int i=0; i<G[now[0]].size() ; i++) {
                                int next[] = new int[2];        // 0 : 노드 번호, 1 : 깊이
                                
                                next[0] = G[now[0]].get(i);
                                next[1] = now[1] + 1;
                                
                                
                                if (isVisited[next[0]] == false) {
                                        isVisited[next[0]] = true;
                                        queue.add(next);
                                }
                                
                                
                        }
                }
        }

}

 

BFS를 이용한 배열 탐색

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

/*
 * 2차원 경로를 탐색해서 특정 지점까지의 최단거리를 구한다.
 * 아래 예제는 (0,0) 에서 시작하고 (5,5) 까지 갔을 때의 최단 거리를 구한다.
 * 
 */


public class BFS3 {
	public static void main(String[] args) {
		/*
		 * BFS 에는 그래프, 방문여부, 큐, now, next 가 필요 함
		 * 
		 * 예상 결과 : 13
		 */
		
		int size = 6;
		
		int[][] M = new int[][]{
				{1,1,1,1,1,1},
				{0,0,1,0,0,1},
				{1,1,1,0,1,1},
				{1,0,0,0,1,0},
				{1,1,1,0,1,0},
				{0,0,1,1,1,1},
		};

		Queue<int[]> queue = new LinkedList<int[]>();
		boolean[][] visited = new boolean[6][6];
		
		int[] now, next;
		
		now = new int[3];
		
		now[0] = 0;
		now[1] = 0;
		now[2] = 1;
		
		queue.add(now);
		visited[now[0]][now[1]] = true;
		
		while (!queue.isEmpty()){
			
			now = queue.poll();
			
			// 탈출 조건
			if (now[0] == 5 && now [1] == 5){
				System.out.println(now[2]);
				break;
			}
			
			// 동
			next = new int[3];
			next[0] = now[0] ;
			next[1] = now[1] + 1;
			next[2] = now[2] + 1;
			
			if (next[1] < size && M[next[0]][next[1]] == 1 && visited[next[0]][next[1]] == false) {
				queue.add(next);
				visited[next[0]][next[1]] = true;
			}
			
			// 서
			next = new int[3];
			next[0] = now[0] ;
			next[1] = now[1] - 1;
			next[2] = now[2] + 1;
			
			if (next[1] >= 0 && M[next[0]][next[1]] == 1 && visited[next[0]][next[1]] == false) {
				queue.add(next);
				visited[next[0]][next[1]] = true;
			}
			
			// 남
			next = new int[3];
			next[0] = now[0] + 1;
			next[1] = now[1] ;
			next[2] = now[2] + 1;
			
			if (next[0] < size && M[next[0]][next[1]] == 1 && visited[next[0]][next[1]] == false) {
				queue.add(next);
				visited[next[0]][next[1]] = true;
			}
			
			// 북
			next = new int[3];
			next[0] = now[0] - 1;
			next[1] = now[1] ;
			next[2] = now[2] + 1;
			
			if (next[0] >= 0 && M[next[0]][next[1]] == 1 && visited[next[0]][next[1]] == false) {
				queue.add(next);
				visited[next[0]][next[1]] = true;
			}
		}
	}
}