BFS (Breath First Search)(너비 우선 탐색)

 

BFS란 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법입니다.

즉 끝까지 깊게 먼저 탐색하는 dfs랑 대비됩니다. 

 

1을 시작으로 bfs탐색을 한다면

(1)->(2->3)->(4->5->6->7) 이런 식으로 탐색을 합니다. 괄호를 친부분은 같은 거리를 표시한 것 입니다. 

즉 괄호 안에서의 탐색 순서는 큐에 넣은 순서에 따라 달라지기 때문에 코드에 따라 달라질 수 있습니다.

 

 

그래프는 vector를 이용하면 쉽게 표현 할 수 있습니다.

위의 그래프는 아래와 같이 표현됩니다.

	a[1].push_back(2); //노드 1에서 노드 2로 연결
	a[1].push_back(3);
	a[2].push_back(1);
	a[2].push_back(3);
	a[2].push_back(4);
	a[2].push_back(5);
	a[3].push_back(1);
	a[3].push_back(2);
	a[3].push_back(6);
	a[3].push_back(7);
	a[4].push_back(2);
	a[4].push_back(5);
	a[5].push_back(2);
	a[5].push_back(4);
	a[6].push_back(3);
	a[6].push_back(7);
	a[7].push_back(3);
	a[7].push_back(6);

 

 

 

 

<전체 코드>

C++

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

vector<int> a[10];
bool check[10];

void bfs(int start)
{
	queue<int> q;
	q.push(start);
	check[start] = true;

	while (!q.empty())
	{
		int node = q.front();   //큐에는 항상 가까운 것부터 저장되게 된다.
		q.pop();

		printf("%d ", node);

		for (int i = 0; i < a[node].size(); i++)
		{
			int next = a[node][i];     //다음 노드
			if (check[next])continue;  //다음 노드가 방문한적이 있으면 스킵
			check[next] = true;      //노드 방문 표시
			q.push(next);           //큐에 저장
		}
	}
}

int main()
{
	a[1].push_back(2); //노드 1에서 노드 2로 연결
	a[1].push_back(3);
	a[2].push_back(1);
	a[2].push_back(3);
	a[2].push_back(4);
	a[2].push_back(5);
	a[3].push_back(1);
	a[3].push_back(2);
	a[3].push_back(6);
	a[3].push_back(7);
	a[4].push_back(2);
	a[4].push_back(5);
	a[5].push_back(2);
	a[5].push_back(4);
	a[6].push_back(3);
	a[6].push_back(7);
	a[7].push_back(3);
	a[7].push_back(6);

	bfs(1);

	return 0;
}

 

코틀린

import java.util.*

var a = Array(10, { mutableListOf<Int>() })
var check = BooleanArray(10,{false})

fun bfs(start:Int) {
    var q :Queue<Int> = LinkedList()
    q.add(start)
    check[start]=true

    while(!q.isEmpty()){
        var node = q.poll()
        print("$node ")
        for(i in 0..a[node].size-1){
            var next = a[node][i]
            if(check[next])continue
            check[next]=true

            q.add(next)
        }
    }
}

fun main() {

    a[1].add(2)
    a[1].add(3)
    a[2].add(1)
    a[2].add(3)
    a[2].add(4)
    a[2].add(5)
    a[3].add(1)
    a[3].add(2)
    a[3].add(6)
    a[3].add(7)
    a[4].add(2)
    a[4].add(5)
    a[5].add(2)
    a[5].add(4)
    a[6].add(3)
    a[6].add(7)
    a[7].add(3)
    a[7].add(6)
    bfs(1)
}

 

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.

 

 

<BFS 연습 문제>

백준 7569번: 토마토 : wlshddlek.tistory.com/42