[이코테] CHAPTER 05 DFS/BFS - BFS(deque 메서드) - Python(파이썬),Java(자바)

DFS 설명

스택, 큐, 재귀함수, DFS

https://www.youtube.com/watch?v=7C9RgOcvkvo

BFS : 너비 우선 탐색 

가까운 노드부터 탐색하는 알고리즘 <-> DFS: 최대한 멀리 있는 노드를 우선으로 탐색하는 방식

   - 큐 자료구조 사용 하는 것이 정석

       1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

       2. 큐에서 노드를 꺼내 해당 노드 중에서 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

       ( BFS는 인접 노드를 한번에 넣는다는 특징을 가지고 있음) 

       3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

'1'을 큐에 삽입하고 방문 처리( 방문 처리된 노드는 회색, 큐에서 꺼내 현재 처리하는 노드는 파란색)

'1'을 큐에서 꺼내고 방문하지 않은 인접 노드인 '2','3','8'을 큐에 삽입 ( 번호가 낮은 노드부터 넣는다고 하였으므로 2부터 넣기)

'2'를 큐에서 꺼내고, 인접 노드인 '7'을 큐에 삽입

'3'을 큐에서 꺼내고, 인접 노드인 '4','5'를 큐에 삽입

'8'을 큐에서 꺼내고, 방문하지 않은 인접 노드가 없으므로 무시

'7'을 큐에서 꺼내고, 인접 노드인 '6'을 큐에 삽입

남아 있는 노드에 방문하지 않은 인접 노드가 없음.따라서 모든 노드를 차례대로 꺼낸다.

1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초실제로 구현함에 있어 deque 라이브러리를 사용하는 것이 좋으며 O(N) 시간 소요 + 일반적으로 DFS 보다 좋은 편

 

https://leonkong.cc/posts/python-deque.html
* 양 끝 엘리먼트에 접근하여 삽입 삭제를 하는 경우, list가 이러한 연산에 O(n)을 소요하는 데 반해, 데크는 O(1)을 소요 * 

 데크(deque) 메서드 
deque.append(item): item을 데크의 오른쪽 끝에 삽입
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제
deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가
deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가
deque.remove(item): item을 데크에서 찾아 삭제
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

Python 이용

from collections import deque

#BFS 메서드의 정의
def bfs(graph,start,visted):
    #큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visted[start]=True
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 가장 먼저 들어온 원소를 뽑기
        v = queue.popleft()
        print(v,end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 노드를 삽입
        for i in graph[v]:
            if not visted[i]:
                queue.append(i)
                visted[i]=True

graph =[
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visted=[False]*9

bfs(graph,1,visted)

결과 화면

Java 이용 ( https://github.com/ndb796/python-for-coding-test/blob/master/5/9.java )

package s14_dfs;

import java.util.*;

public class e5_9 {

    public static boolean[] visted = new boolean[];
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    //BFS 함수 정의
    public static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        //원소를 넣을 때
        q.offer(start);
        //현재 노드를 방문 처리
        visted[start] =true;
        //큐가 빌때까지 반복
        while(!q.isEmpty()){
            //큐에서 하나의 원소를 뽑아 출력
            int x = q.poll();
            System.out.print(x+" ");
            //해당 원소와 연결된, 아직 방문하지 않은 우너소들을 큐에 삽입
            for(int i=0;i<graph.get(x).size();i++){
                int y = graph.get(x).get(i)//인접한 노드들
                if(!visted[y]){//방문하지 않았을 때
                    q.offer(y);
                    visted[y]=true;
                }
            }
        }
    }

    public static void main(String[] args) {
        //그래프 초기화
        for(int i=0;i<9;i++){
            graph.add(new ArrayList<Integer>());
        }
        // 노드 1에 연결된 노드 정보 저장 
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(1).add(8);

        // 노드 2에 연결된 노드 정보 저장 
        graph.get(2).add(1);
        graph.get(2).add(7);

        // 노드 3에 연결된 노드 정보 저장 
        graph.get(3).add(1);
        graph.get(3).add(4);
        graph.get(3).add(5);

        // 노드 4에 연결된 노드 정보 저장 
        graph.get(4).add(3);
        graph.get(4).add(5);

        // 노드 5에 연결된 노드 정보 저장 
        graph.get(5).add(3);
        graph.get(5).add(4);

        // 노드 6에 연결된 노드 정보 저장 
        graph.get(6).add(7);

        // 노드 7에 연결된 노드 정보 저장 
        graph.get(7).add(2);
        graph.get(7).add(6);
        graph.get(7).add(8);

        // 노드 8에 연결된 노드 정보 저장 
        graph.get(8).add(1);
        graph.get(8).add(7);

        bfs(1);
    }
}

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용