[알고리즘] java로 BFS 구현하기

BFS(너비우선탐색)로 최단거리를 구하는 JAVA코드를 구현해보도록 하겠습니다.

 

BFS의 경우 특정위치를 기준으로 인접한 노드를 모두 방문하며 한 번 방문했던 노드는

방문 이력을 저장해가면서 다음 노드, 다음노드로 넘어가 전체를 검색하는 방법입니다.

 

BFS는 QUEUE를 활용해서 구현할 수 있습니다. 

 

특정위치의 인접한 노드를 먼저 모두 확인해야되기 때문에 인접한 노드를 모두 큐에 넣고 인접노드를 모두 큐에 넣었을때 꺼내면서 방문여부를 기록해주면됩니다.

 

아래는 최단거리 검색 예제를 통해 JAVA로 BFS를 구현해보도록 하겠습니다.

 

bfs.txt파일에는 아래와 같이 첫번째 열에 행과 열을 표시해주고

다음 라인부터 행/열에 맞는 배열이 생성됩니다. (1 : 이동가능 ,0 : 이동불가)

 

 

아래 샘플에서는 0,0 지점에서 마지막 4,6 지점까지 가는 최단거리를 출력하는 코드입니다.

 

1의 경우 인접한 노드라고 생각하면되고, 0 은 인접하지 않은 노드로 보면 됩니다.

 

그럼 실제로 bfs로 최단거리를 찾는 코드를 구현해보겠습니다.

 

package com.company;

        import java.io.FileInputStream;
        import java.util.*;

public class Main {

    static int N =0; //행
    static int M =0; //열
    static int[][] arr;
    static boolean[][] visited;

    public static void main(String[] args) {

        try{

			// Scanner sc = new Scanner(System.in);
            Scanner sc = new Scanner(new FileInputStream("C:\\Users\\vmpo\\Desktop\\bfs.txt"));

            N = sc.nextInt();
            M = sc.nextInt();
            sc.nextLine();

            arr = new int[N][M];
            visited = new boolean[N][M];

            for (int i = 0; i < N; i++) {
                String str = sc.nextLine();
                for (int j = 0; j < M; j++) {
                    arr[i][j] = str.charAt(j)-'0';
                    visited[i][j] = false;
                }
            }

            visited[0][0] = true;
            BFS(0, 0);

        }catch (Exception e){
            System.out.println(e.toString());
            e.printStackTrace();
        }

    }

    static void BFS(int start, int end){

        try{

            Queue<Node> q = new LinkedList<>();
			//최초 queue 삽입
            q.add(new Node(start,end,1));

            while(!q.isEmpty()){

                Node node = q.poll();
                visited[node.x][node.y] = true;
                System.out.println(node.x + "," +node.y );
				//상하좌우 이동 가능여부를 확인해본다.

				//좌
                if(node.y-1 >= 0 && node.y-1 < M && arr[node.x][node.y-1] == 1 && visited[node.x][node.y-1] == false){
                    q.add(new Node(node.x,node.y-1,node.depth+1));
                }

				//우
                if(node.y+1 >= 0 && node.y+1 < M &&arr[node.x][node.y+1] == 1 && visited[node.x][node.y+1] == false){
                    q.add(new Node(node.x,node.y+1,node.depth+1));
                }

				//위	
                if(node.x-1 >= 0 && node.x-1 < N &&arr[node.x-1][node.y] == 1 && visited[node.x-1][node.y] == false){
                    q.add(new Node(node.x-1,node.y,node.depth+1));
                }

				//아래
                if(node.x+1 >= 0 && node.x+1 < N && arr[node.x+1][node.y] == 1 && visited[node.x+1][node.y] == false){
                    q.add(new Node(node.x+1, node.y,node.depth+1));
                }

                if(visited[N-1][M-1]){
                    System.out.println("완료");
                    System.out.println(node.depth);
                    break;
                }

            }

        }catch (Exception e){
            System.out.println(e.toString());
        }
    }

}

class Node{
    int x;
    int y;
    int depth;

    Node(int _x, int _y, int _depth){
        this.x = _x;
        this.y = _y;
        this.depth = _depth;
    }
}

 

1. Node클래스를 생성합니다.

 x좌표, y좌표를 의미하는 멤버변수 int x,y 와 해당 노드까지 오는데 몇번이 걸렸는지를 의미하는 int depth를 선언합니다.

 

2. Node가 저장될 Queue를 선언합니다. 그리고 0,0에 depth는 1로 초기화한 Node 객체를 큐에 넣어줍니다.

  Queue q = new LinkedList<>();
  //최초 queue 삽입
  q.add(new Node(start,end,1));

 

3. while문에는 q안에 데이터 존재 여부를 체크하며 반복하게됩니다. 루프 내에서는

상,하,좌,우에 접근할 수 있는 노드가 있는지(위에서는 "1"이 있는지) 확인해줍니다. "1"이 있는 경우라면 해당 노드의 좌표를 queue에 넣어줍니다. queue에 넣어줄때는 x,y좌표와 함께 depth를 앞의 노드 +1 을 해줍니다.

 

queue에 넣으면 넣은 순서대로(선입선출) 다시 검색이 시작되기 때문에 인접노드를 모두 queue에 담은 후에 다시 처음 넣었던 노드를 중심으로 인접노드를 다시 검색하게 됩니다.

 

4. 이렇게 전체를 검색하고 최종 지점(위에서는 (4,6))좌표에 이동해서 방문체크가 완료된다면, 

   종료하고 4,6좌표 노드의 depth를 출력해줍니다. depth값이 결국 최단거리로 이동한 값이 됩니다.

 

위 과정이 완료되면 최종적으로 depth , 즉 최단거리 값이 출력됩니다.