BFS 알고리즘 공부

 

 

알고리즘 이론을 정말 정말 오랜만에 다시 공부해보면서 첫번째로 그동안 부족하다고 느꼈던 탐색쪽을 공부했다.

 

---

 

BFS(너비 우선 탐색)

1. 그래프 이론이자 완전탐색 방법 중 하나이다.
2. BFS은 너비 우선 탐색으로 가까운 노드를 우선적으로 방문하고 탐색한다.
   • 그래프에서 인접하게 연결된 노드부터 쭉 방문한 후 그 다음으로 인접된 노드들을 순차적으로 방문하는 방식이다.
   • 뎁스가 낮은(가까운) 노드부터 쭉 방문한 후 뎁스를 높여가는게 특징.
3. Queue의 구조를 사용하는 방식
4. 최단 거리 찾기와 같은 문제에서 자주 나온다고 한다.

 

* 이론 공부는 youtu.be/CJiF-muKz30 을 참고했다. 설명을 쉽게 잘 해주신다.

 

---

 

Queue를 사용한 BFS

int[][] graph = {
  {},
  {2, 3, 8},
  {1, 7}, 
  {1, 4, 5},
  {3, 5},
  {3, 4},
  {7}, 
  {2,6,8}, 
  {1, 7}
};

boolean[] visited = new boolean[graph.length]; 

Queue<Integer> que = new LinkedList<Integer>();

int num = 1;
que.add(num);		// 방문했다는 의미로 추가
visited[num] = true;

while(!que.isEmpty()) {		// while을 사용한 이유 : 배열의 원소를 순차적으로 방문하는 for문이 적합하지 않음. 모두 방문했다는 조건이 만족할 때 반복을 종료할것이므로 while을 사용
    num = que.poll();		// 첫번째 원소 빼기. 이 원소의 연결 노드를 다시 큐에 담을거임  
    System.out.println(num);		// 방문했당.

    for(int i=0 ; i<graph[num].length ; i++) { // 연결된 노드를 순차적으로 큐에 추가
      int linkNode = graph[num][i];
      if(visited[linkNode] == false) {		// 연결 된 노드가 아직 방문하지 않았고, 방문계획이 없으면
        que.offer(linkNode);				// 큐에 추가 
        visited[linkNode] = true;			// 방문했음
      }
  }
}