[백준 1260번] DFS와 BFS |그래프의 탐색법|

https://www.acmicpc.net/problem/12600

1260번: DFS와 BFS

___________________________________________________

입력 

1.정점의 개수 N(1 ≤ N ≤ 1,000), 

2.간선의 개수 M(1 ≤ M ≤ 10,000)

3.탐색 시작정점

간선은 양방향

___________________________________________________

출력

목표: 방문순서 출력하기.

단, 방문순서는 노드의 번호가 작은순서 우선으로 방문한다.

(생각해 볼수 있는것)

1.애초에 자료구조에 들어갈때 작은것이 맨위로 올라가게끔

저장하는 자료구조? priority queue BFS에는 유용하겠다.

2.아니면 일단 넣고... 각각 노드를 기준으로 각각 next노드들을

sort하는 방법?

___________________________________________________

필요한 자료구조들

벡터

그래프를 만들기 위해서

방문배열을 만들기 위해서

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

큐

BFS를 만들기 위해서.

___________________________________________________

for문의 다양한 사용법

1.for(int nxt :G[node] )

https://boycoding.tistory.com/210

C++ 07.18 - 범위 기반 for 문 (range-based for statement)

2.이터레이터

https://hyeonstorage.tistory.com/318

[STL] 반복자 iterator 개념 및 예제

___________________________________________________

생각방법.

A.그래프 만들기

양방향 간선이므로

1->2 있으면 2->1도 있어야한다.

사실.. 정대각 행렬들을 기준으로 선대칭이다.

B.탐색방법 설계

___________________________________________

ⓐDFS는 재귀적인 탐색을하면된다.

#재귀 : 탐색 

#for : next 주변 노드 고르기

#is visit? : yes or no

1.DFS(시작정점);

2.시작정점은 방문되었다.

visit[cur_node] = true;

3.다음노드를 살펴보자.

_

| for문을 사용할것이다.

| {

| G[node] 의 자식노드를 살펴본다는것은..

| G[node][0], G[node][1], G[node][2], G[node][3] .... G[node][size]

| 즉, "G[node]"의 배열의 크기만큼  싸그리 둘러본다는 동작.

| }

|

| 살펴볼때 기준

| 이미 방문되었나?

| no이면 들어간다. 재귀 DFS(next_node)

| yes이면 다른정점을 찾거나 빠져나온다. 재귀에서

|

ㄴ

ⓐ+1 DFS의 방문순서는 어떻게 알지??

방문체크 visit이 되는순간마다

cout을 하면 될듯 ㅋ

___________________________________________

ⓑBFS는 큐의 push pop을 이용해서 탐색한다.

DFS와는 다르게.. 이건 BFS만을 위한 queue 자료구조를

따로 한번 만들어줘야 한다.

#while : queue가 빌때까지

#for : next 주변 노드 고르기

#is visit? : yes or no

1.BFS(시작정점);

2.queue push(시작정점)

3.while(queue가 아직 뭔가 채워져있나?)

{

-채워쳐 있는 원소 front값 (정점번호)하나 가져오고 

(정점번호를 popnode라고 하면)

그다음 pop한다.

-for문으로 popnode 의 주변노드 next_node를 고른다.

{

고른 next_node가 이미 방문되었나?

no : queue push(next_node)

visit[next_node] = true;

yes : 이면 다른정점을 찾아 for continue;

}

}

_______________________________________________

코드 https://colorscripter.com/

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
 
using namespace std;
 
//입력_________________________________
int N,M,S; 
/* 
    N:정점 개수
    M:간선 개수
    S:시작정점
        예를들어서.. DFS(S); 또는 BFS(S);
*/
//_________________________________
 
 
//배열_________________________________
vector<int> G[1001];
bool D_visit[1001];
bool B_visit[1001];
queue<int> BFS_queue;
 
//_________________________________
 
void DFS(int cur)
{
    D_visit[cur] = true;
    cout << cur << ' ';
 
    for (vector<int>::iterator it = G[cur].begin(); it != G[cur].end(); it++)
    {
        int nxt = *it;
        if(!D_visit[nxt])
            DFS(nxt);
    }
}
 
void BFS(int cur)
{
 
    B_visit[cur] = true;
    BFS_queue.push(cur);
 
    while (!BFS_queue.empty())
    {
        int cur_node = BFS_queue.front();
        BFS_queue.pop();
 
        B_visit[cur_node] = true;
        cout << cur_node << ' ';
 
        for (int nxt : G[cur_node])
        {
            if (!B_visit[nxt])
            {
                BFS_queue.push(nxt);
                B_visit[nxt] = true;
            }
        }
    }
}
 
int main()
{
    
    cin >> N >> M >> S;
 
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
 
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 0; i < N; i++)
    {
        sort(G[i].begin(), G[i].end());
    }
 
    DFS(S);
    cout << '\n';
    BFS(S);
}