20170126 백준 1260 DFS BFS

20170126

 백준 1260번 DFS & BFS

기본적인 DFS BFS문제.

중요 한 것은 DFS BFS 함수를 구현하는것

입력시 주의할점 

1) 간선은 양방향

2) 방문할 수 있는 정점이 여러점인경우 정점번호가 작은것 부터 탐색

함수 구현하기 위해서는 :

간선의 개수(M), 정점의 개수(N),  탐색 시작할 노드(V), 노드 탐색의 유무 체크 배열(bool type), 

노드끼리 연결성 보여주는 배열(vector) , BFS함수에서 사용되는 queue 

가 대표적으로 필요하다.

모든 함수의 선언 이전에 필요한 변수, 배열을 선언하고, 헤더를 추가하자

#include<iostream>  

#include<cstring> --> memset( ) 를 쓰기 위함

#include<algorithm> --> sort( )

#include<vector> --> vector<int> adj[1001]

#include<queue> --> BFS함수중 qsearch선언에 필요 

using namespace std;

bool chk[1005]; --> 각 노트 방문 유무 체크를 위한 bool type배열 (따로 초기화 안해줄시 default값은 false)

vector <int> adj[1001]; --> relationships between node1 and node2

main( ) 에서는   M, N, V를 입력 받고, 노드 끼리의 연결성을 보여주는 배열(노드1, 노드2)을 입력하자. 

후, 이 문제의 목적인 DFS BFS를 호출하자.

int main( ) {

int N, M, firstNum; // fisrtNum = V

int ss, ee; // node 1, node 2

cin >> N >> M >> firstNum;

for (int i = 0; i < M; i++) {

cin >> ss >> ee;

adj[ss].push_back(ee); //vector이므로 push_back(x) 을 이용

adj[ee].push_back(ss);

}

for (int i = 0; i <= N; i++) {

sort(adj[i].begin(), adj[i].end()); 

}

DFS(firstNum);

cout << "\n";

memset(chk, false, sizeof(chk));

BFS(firstNum);

cout << "\n";

return 0;

}

여기서 adj[ss].push_back(ee), adj[ee].push_back(ss);를 함으로써 

ss ee 입력을 순서대로 1 2 / 1 3/ 2 3 받았다고 가정해보자.

> adj[1][0] = 2; 

   adj[2][0] = 1;

> adj[1][1] = 3;

   adj[3][0] = 1;

> adj[2][1] = 3;

   adj[3][1] = 2;

로 입력이 된다. // vector의 특성 이용: non-static

sort( ) 를 통해 각 adj[i][0] , adj[i][1] … 를 오름차순으로 정렬

후 DFS함수 호출 > memset( ) 을 통해 chk배열의 초기화( > false) > BFS함수 호출

DFS함수의 구현

DFS :  깊이 우선 탐색

1 ㅡ 2ㅡ 3

ㅣ 

4 ㅡ 5

위와 같은 그래프가 있다고 가정하면 

탐색 순서  :  1 > 2 > 3 > (2) > (1) > 4 > 5

하나의 노드를 집중해서 끝까지 탐색 하고 나서야 다시 돌아와 연결되있던 다른 노드를 탐색한다

DFS는 대표적으로 재귀호출이다

void DFS(int cur) {

cout << cur << " ";

chk[cur] = true;

for (int i = 0; i < adj[cur].size(); i++) {

int next = adj[cur][i];

if (chk[next] == false) {

DFS(next);

}

}

}

탐색 순서를 알기 위해 첫줄에는 현재 탐색 중인 노드를 출력한다.

노드를 탐색했다는 표시를 하기위해(중복 탐색 방지) chk[cur] = true; 로 바꿔준다.

그 후 각 adj[cur]에 연결 되어있는 노드를 확인한다.

cur이 1 일 경우 : 

adj[1][0] = 2;

adj[1][1] = 4;

이때, next는 adj[i][j] 를 보기 좋게 표현하기 위한 편의를 위한 것으로 필수적인 요소는 아니다. 

for문 안에서 adj[1][0] 값인 2, 노드(= next) 2에 탐색 유무를 체크.

노드 2가 탐색이 안되어있다면 (chk[next] == false) 

DFS(next)를 재귀로 호출해준다.

> cur : 1-> 2 로 변경후 위와 같은 과정이 반복된다.

1-> 2-> 3 까지 탐색을 다 하고 난 후에는

i++ --> next  = adj[1][1] 후 같은 작업 반복.   

마지막 노드까지 전부 탐색 하고 나면 끝. 

BFS함수의 구현

BFS: 넓이 우선 탐색

1 ㅡ 2ㅡ 3

ㅣ 

4 ㅡ 5

위와 같은 그래프가 있다고 가정하자. (DFS와 동일그래프)

이때 탐색 (출력) 순서는 다음과 같다 :

1 > 2 > 4 >3 > 5

BFS의 특성은 각 노드에 연결되어있는 모든 노드를 탐색 하고 나서야 다음 단계(깊이)로 넘어간다

void BFS(int start) {

queue<int> qsearch;

chk[start] = true;

qsearch.push(start);

while (!qsearch.empty()) {

int node = qsearch.front();

qsearch.pop();

cout << node<<" ";

for (int i = 0; i < adj[node].size(); i++) {

int next = adj[node][i]; // 보기 편하라고 

if (chk[next] == false) {

chk[next] = true;

qsearch.push(next);

}

}

}

}

BFS함수 구현에는 큐가 필요하다

*큐(queue) 

first in first out 의 특성을 지닌 STL 중 하나이다

메인함수에서 BFS함수가 처음으로 호출이 되면, 우선, 탐색시작 정점의 탐색 유무가 체크 된다.

후, 큐 안에 그 노드를 넣는다. 

     ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

(앞)  1                           (뒤)

    ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위와 같은 상태가 된다. 그 후, 큐 안에가 비어있지 않음을 체크 한후, !qsearch.empty( ) 일경우

while문안을 실행한다.

큐 맨 앞에 있는 값을 변수 node에 옮긴 후, 맨 앞 값을 pop해준다.

  node = 1

     ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

(앞)                              (뒤)

    ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

그 후 문제에서 요구한 대로 현재 탐색하고 있는 노드의 값을 출력해주고

노드에 연결되어있는 노드들을 탐색한다.

*adj[i]가 입력되는 과정은 DFS함수의 구현을 참고하자.

변수 next에 adj[node][i]를 입력해주자. 이는 필수적인 것이 아닌 표현의 편의성을 위한 것이다.

node에 연결되어 있는 next노드가 이미 탐색이 되어있는지 체크를 해주고, 탐색이 아직 되지 않았다면, chk[next] = true 로 만들어 탐색을 해줬다고 

체크를 하고, 큐 안에 next 값을 넣는다. 후 DFS와는 다르게 재귀가 아닌, i++ 후 반복문을 다시 시행한다

정점 1 에는 2개의 정점이 연결되어있으니 반복문도 두번 반복한다.

두번의 반복문 후에 큐 상태는 이렇다.

     ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

(앞) 2 4                          (뒤)

    ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

후 다시 while문으로 돌아가 위와 같은 작업을 반복하면 된다. 

여기서, 큐에 쌓인 순서대로 앞에서 부터 탐색을 이어간다.

그렇기 때문에 BFS의 탐색 순서는 1 > 2 > 4 > 3 > 5 이다.