17. 너비 우선 탐색(BFS Algorithm)

  이번 시간에는 탐색 중에서 대표적 알고리즘인 BFS(Breadth First Search)에 대해 알아보도록하자. DFS와 더불어서 프로그래밍 문제를 푸는데 정말 많이 쓰이게 되는 알고리즘이다. 트리구조로 구성된 노드를 탐색할 때 자신을 기분으로 주변에 있는 노드를 모드 검색하는 방법이다. 따라서 너비 우선 탐색이라고 하고, 반대되는 개념인 깊이 우선 탐색은 연결된 끝까지 탐색을 하는 방식이다. 

1. BFS Algorithm 방문순서

  너비 우선 탐색은 시작 노드로 부터 연결된 모든 노드를 Queue에 넣고 다음 노트를 선택하는 방식이다. 이 과정을 반복하면서 계속 다음 노드를 선택한다. 아래 예시를 보면서 설명하도록 하자.

  시작 노드를 1번이라고 하면 Queue에 2, 3, 4번 정점을 넣게 된다.

  그 다음 2번노드를 방문해 아직 방문하지 않은 5번 노드를 다시 Queue에 넣게된다. 3번 노드는 이미 Queue에 존재하므로 다시 방문하지 않는다. 이렇게 하면 다음과 같은 순서대로 1번부터 8번 노드를 방문하게 된다.

  

1번 노드로 부터 2, 3, 4번 노드를 순차적으로 방문한 뒤 2번에서 5번노드, 3번에서 6, 7번 노드, 4번에서 8번 노드를 방문한다.

따라서, 위와 같은 순서대로 탐색을 실시하게 된다.

조금 더 상세하게 방문 순서를 살펴보면,

우선 1번 시작 노드에 도달 했을 경우 인접한 노드를 Queue에 넣게 된다.

Queue : 2, 3, 4

Queue 맨 앞에 있는 2번을 방문하게 되고, 2에 인접한 5번 노드를 Queue에 넣게 된다. 3번은 이미 Queue안에 있으므로 따로 넣지 않는다.

Queue : 3, 4, 5

그 다음 Queue 가장 앞에 있는 3번 노드를 방문하고 3번과 인접한 노드를 Queue에 넣게 된다.

Queue : 4, 5, 6, 7

이 과정을 계속 반복한다.

Queue : 5, 6, 7, 8

남은 순서대로 방문을 하게 되면 BFS가 종료 된다.

2. BFS 구현

BFS를 Java로 코딩하게 되면 다음과 같다.

package bfs;
 
import java.util.*;
 
public class Soultion {
 
    public static int size;
    public static int map[][];
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        
        // 입력 변수
        System.out.println("Size를 입력하시오:");
        size = sc.nextInt();
        
        map = new int [size][size];
        
        int a, b;
        System.out.println("간선을 입력하시오(종료 -1, -1):");
        while (true){
            a=sc.nextInt();
            b=sc.nextInt();
            if(a == -1 && b == -1) break;
            map[a][b]=1;
        }
        
        Bfs bfs = new Bfs(0,size,map);
        System.out.println("이동 순서");
        bfs.BfsAction();
    
    }
 
}
 
class Bfs{
    
    int start;
    int size;
    public static int[] token;
    public static int[][] map;
    
    Bfs(int a, int b, int[][] map){
        start = a;
        size = b;
        Bfs.map = map;
    }
    
    public void BfsAction(){
 
        // 방문 여부 저장
        token = new int[size];
        // start 정점 방문 표시
        token[start] = 1;
        // 큐 생성
        Queue<Integer> queue = new LinkedList<Integer>();
        // 시작 점 큐 입력
        queue.add(start);
        System.out.println(start);
        
        // Bfs 탐색 
        while(!queue.isEmpty()){
            // 큐에서 값 뺴오기
            int temp = queue.poll();
            // 0~size 탐색
            for(int i = 0; i<size ;i++){
                // 길이 존재하고 방문하지 않았다면
                if(map[temp][i]==1 && token[i]==0){
                    // 큐에 추가
                    queue.add(i);
                    // 이동
                    System.out.println(i);
                    token[temp]=1;
                }
            }
        }
        
    }
    
}

이 코드의 결과는 아래와 같이 나온다.

3. BFS 응용

  BFS를 이용한 문제를 한번 풀어보자. 아래와 같은 경로로 이동하여 최단 거리를 구하는 프로그램을 한번 구해보자.

  위의 사진처럼 S에서 시작해 D로 가는 미로가 존재한다고 가정하자. 이 문제를 아래의 코드를 통해 최단거리를 분석할 수 있다.

  BFS알고리즘으로 문제를 해결하기 위해서는 반드시 Queue를 사용해야 한다. Queue에 대한 라이브러리가 존재하는 java 언어의 경우 미래 정의 된 함수를 사용하면 간편하게 BFS를 구현할 수 있다. 이때, Queue에서 Peek와 Poll의 차이를 정확히 파악할 줄 알아야한다.

Peek() : Queue에 가장 끝에 있는 객체를 반환하나, Queue에서 제거하지는 않는다.

Poll() : Queue에 가장 끝에 있는 객체를 반환하고 Queue에서 제거한다.

이 두 함수를 잘 활용한다면 BFS 관련 문제를 쉽게 풀 수 있다.

package bfsproblem;
 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Solution {
 
   public static void main(String[] args) {
      // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        // mapsize 입력
        int size = sc.nextInt();
        
        // map 입력
        int[][] map = new int[size][size];
        Vertex[][] vertex = new Vertex[size][size]; 
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                // vertex 정의
                vertex[i][j]=new Vertex();
                vertex[i][j].x=i;    
                vertex[i][j].y=j;
            
            }
        }
        
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){        
                // map 생성
                map[i][j]=sc.nextInt();
                // 0인 경우 길이 없고, 1인 경우 길이 있다.
            }
        }
        
        //BFS를 위한 큐 생성
        Queue<Vertex> queue = new LinkedList<Vertex>();
        
        // Vertex 시작점 정의하기
        vertex[0][0].dist = 1;
        
        // 큐에 삽입
        queue.add(vertex[0][0]);
                      
        while(!queue.isEmpty()){
            // 큐에 vertex가 없으면 종료
            if(queue.peek()==null){ 
                System.out.println("더이상 길이 없습니다.");
                break;
            }
            
            // Vertex에서 위치 가져오기
            int x = queue.peek().x;
            int y = queue.peek().y;
            int dist = queue.peek().dist;
            
            // 도착점에 도착하면 종료
            if(x==size-1 && y==size-1){
                System.out.println("도착점입니다.");
                System.out.println("거리: "+dist);
                break;
            }
            
            // 방문 Vertex의 경우 넘어간다.
            if(queue.peek().visited==true){
                queue.poll();
                continue;
            }
            // 방문하지 않았다면, 방문처리 한 뒤 연산을 수행한다.
            else{
                queue.peek().visited=true;
            }
            
            // 위쪽 탐색
            if(x!=0 && map[x-1][y]==1){
                vertex[x-1][y].dist = dist+1;
                queue.add(vertex[x-1][y]);
              }
            
            // 아래쪽 탐색
            if(x!=size-1 && map[x+1][y]==1){
                vertex[x+1][y].dist = dist+1;
                queue.add(vertex[x+1][y]);
            }
            // 좌측 탐색
            if(y!=0 && map[x][y-1]==1){
                vertex[x][y-1].dist = dist+1;
                queue.add(vertex[x][y-1]);
            }
            
            // 우측 탐색
            if(y!=size-1 && map[x][y+1]==1){
                vertex[x][y+1].dist = dist+1;
                queue.add(vertex[x][y+1]);
            }
            
            // 탐색 후 큐에서 제거 함
            queue.poll();
        }
        
   }     
   
}
 
class Vertex{
   //초기 인덱스 
    int x=-1; int y=-1;
    //연결 Vertex
    LinkedList<Vertex> linkedList=new LinkedList<Vertex>();
    int dist=-1;
     
    boolean visited=false;
     
    }