탐색 : BFS 이론과 문제

I. 탐색

탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다.

탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다

탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프 표현에 대해서 공부가 필요하다

 

II. 너비 우선 탐색(BFS : breadth - first serach) 이론

1.  들어가며

가장가까운 노드부터 우선하는 점이 BFS과 비교가 된다.

 

(1) 정의

1)

DFS란 그래프 완전탐색기법 중 하나이다.

 

그래프의 시작노드(a)에서 출발 

-> 시작노드와 가까운 노드(b) 먼저 방문 -> 시작노드와 가까운 다른노드(c) 방문

-> b노드와 가까운 노드(d) 방문 -> 반복

 

이러한 연유로 목표노드에 도착하는 경로가 여러개일 때 '최단경로'를 보장한다

 

2) 특징

가까운노드를 먼저 방문하기 때문에 큐를 이용해서 구현한다.

★ 이유는 인접한 노드를 반복적으로 큐에 넣도록 하면 자연스럽게 먼저들어온것이 먼저 나가기 때문이다.

 

3) 시간복잡도 (노드 수 : V (vertex), E (edge))

O(V + E) 의 시간복잡도를 가진다.

 

 

4) 응용문제

 

 

(2) 핵심이론

1) DFS와 자료형 제외 동일

a. 노드 방문 여부 체크할 배열필요 (한번방문한 노드 다시 방문하면 안됨 : X 일시 무한 loop 빠짐)

b. 그래프는 인접리스트로 표현

c. DFS는 FIFO 이므로 큐를 이용한다

 

2) DFS와 동일

 

< 정리하면 >

큐에 노드 삽입(push)시 방문 배열을 체크

큐에 노드 뺄(pop)때 탐색 순서에 기록한다

이 경우 인접 노드를 방문 배열과 대조하여 살펴본다.

 

(3) Logic

1) BFS를 시작할 노드 정한후 사용할 자료구조 초기화

 

DFS와 동일하다 다만 큐를 사용할 뿐이다.

a. 초기작업으로 인접리스트로 그래프 표현

 

b. 방문배열 초기화

c. 시작 노드 '큐'에 삽입

2) 큐에서 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

 

a. 큐에서 노드를 꺼내면서 인접노드를 큐에 삽입한다.

노드를 꺼낼 때, 방문배열을 체크해서 방문한노드가 다시 큐에 삽입되지 않게끔 한다.

 

 

b. 꺼낸 노드의 인접노드를 다시 큐에 삽입한다.

 

c. 2,3 을 큐에 삽입하며 방문배열에 체크한다.

3) 큐 자료구조에 값이 없을 때 까지 반복하기

큐에 노드가 없을 때 까지 반복한다. 

선입선출 방식이기 때문에 DFS와 다른점을 확인하자.

 

 

 

 

II. 너비 우선 탐색(DFS : breadth-first serach) - 문제 1

 

[ 백준 1260 ]

1. 문제설명

 

2. 문제풀이

(1) 문제분석

• 노드의 최대 개수 1000개 이다. 시간복잡도가 N^2 이하 알고리즘 모두 사용가능하다
• 문제의 조건에서 노드번호가 작은것부터 먼저 방문한다고 했으므로 오름차순으로 정렬 후 이용해야한다

 

(2) 손으로 풀기

- 블로그에서 생략

(3) 슈도코드 코드 작성

- 블로그에서 생략

(4) 코드 구현 

1) 

package datastructrue5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P1260 {

    private  static ArrayList<Integer>[] A;
    private  static  boolean[] visited;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        //입력
        int N = Integer.parseInt(st.nextToken()); // 노드
        int M = Integer.parseInt(st.nextToken()); //에지
        int V = Integer.parseInt(st.nextToken()); //시작노드

        A = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        int a = 0;
        int b = 0;

        //초기화
        for(int i = 1 ; i < N + 1 ; i++){ //노드 갯수만큼 반복
            A[i] = new ArrayList<Integer>();
        }

        //
        for(int i = 1 ; i < M+1 ; i ++){ //에지 갯수만큼 반복
            st = new StringTokenizer(br.readLine());
            a =  Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            //양쪽에 연결완료
            A[a].add(b);
            A[b].add(a);
        }

//boolean 초기화 하면 false가 기본인줄 몰랐음
                // 각 노드별 탐색시작
        //        for(int i = 1 ; i < N + 1 ; i++) {

        //            visited[i] = false; //초기화

        //        }

        //순서대비 (오름차순 정렬)
        for(int i = 1 ; i < N + 1 ; i++){
            Collections.sort(A[i]);
        }

        visited = new boolean[N+1];

// 연결요소 처럼 그래프가 여러개인 경우 이용하는 것임
//        for(int i = 1 ; i < N + 1 ; i++){

//            if(! visited[i])
                dfs(V);
//        }
        System.out.println();

        visited = new boolean[N+1];
        bfs(V);
        System.out.println();

    }

    private static void dfs(int v) {
        System.out.print(v + "  ");

//        //방문확인
        if(visited[v]) return ;

//
//
//        //인접노드들의 방문체크
//        visited[v + 1] = true;
//
//
//        for(int i = 1 ; i < A.length + 1 ; i++)
//            dfs(i);
//
//        return v;
//        if(visited[v+1]) return;

        visited[v] = true;

        for(int i : A[v])
            if(!visited[i]) dfs(i);

    }

    private static void bfs(int v) {
        //큐 선언
        Queue<Integer> queue = new LinkedList<Integer>();

    //1
        //큐에 삽입 시   // 방문배열에 남기기
        queue.add(v); visited[v] = true;

    //2
        //while 쓰는 이유는 재귀함수가 아니라 queue를 쓰기 때문
        //큐가 빌 때 까지 반복
        while (!queue.isEmpty()){

    //3
            //큐에서 꺼낸다. // 방문순서 출력하
            int now_Node = queue.poll(); System.out.print(now_Node + "  ");

    //4
            //꺼내느 노드의 인접노드를 탐색한다.
            for(int i : A[now_Node]){

    //5
                //인접노드가 방문하지 않았으면
                if(!visited[i]) {
                    //방문배열에 남기고
                    //큐에 넣는다./
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

4. 보충 및 회고 

(1) 보충

1)

연결리스트를 이용해서 큐를 구현하는것에서 선언하는 방식이 특이했다

배열로도 이용할수 있는 방식이 있으면서 연결리스트로한다는게 낯선것이 연달아 와서 그런것 같다

 

즉 참조형식은 Queue, 객체형식은 연결리스트 였다 마치... 상속처럼

 

 

(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.

1)

DFS 는 4단계

BFS 는 5단계 라는것을 잊지말자!!

 

 

DFS는 재귀함수 방식(스택) BFS는 큐 방식이다

이에따라서 DFS는 while이 필요가 없지만, BFS는 큐가 빌 때 까지 확인하기 위한 반복문이 요했다

 

 

2)

오름차순 정렬은 collections.sort() 라는 메소드가 있어서 신기했다.

 

3)

boolean 초기화 하면 초기값은 false라는것이 신기하다

 

 

4)

DFS는 이해했다고 했는데 또 잊었다 유의하자

 

 

 

---

 

 

 

 

---

1. 보충

 

 

2. 회고 

1) 재귀함수 방식으로 익숙하다가 큐로 구현한점은 낯설긴하다