bfs와 dfs를 구현해보았다.

동빈나님의 알고리즘 강의를 참고했다.

 

 

#include<iostream>
#include<queue>
#include<vector>
 
int number=7;
int checked[7];
std::vector<int> vertex[8];
 
void bfs(int start)
{
    std::queue<int> queue;
    queue.push(start);
    checked[start]=true;
    
    while(!queue.empty())
    {
        int searched=queue.front();
        queue.pop();
        std::cout<<searched<<' ';
        
        for(int i=0; i<vertex[searched].size(); i++) //vertex와 연결된 정점들을 for문으로 순회한다. 
        {
            if(!checked[vertex[searched][i]]) //만약 vertex와 연결된 정점이 체크되어있지 않으면 
            {
                queue.push(vertex[searched][i]); //해당 정점을 queue에 넣는다. 
                checked[vertex[searched][i]]=true; //해당 정점을 체크한다. 
            }
        }
    }
}
 
int main(void)
{ 
    vertex[1].push_back(2);
    vertex[2].push_back(1);
    
    vertex[1].push_back(3);
    vertex[3].push_back(1);
    
    vertex[2].push_back(3);
    vertex[3].push_back(2);
    
    vertex[2].push_back(4);
    vertex[4].push_back(2);
    
    vertex[3].push_back(6);
    vertex[6].push_back(3);
    
    vertex[3].push_back(7);
    vertex[7].push_back(3);
    
    vertex[4].push_back(5);
    vertex[5].push_back(4);
    
    vertex[6].push_back(7);
    vertex[7].push_back(6);
    
    bfs(1);
    return 0;
}

..

#include<iostream>
#include<vector>
int number = 7;
int checked[8];
std::vector<int> versus[8];
 
void dfs(int x)
{
    if (checked[x])
    {
        return;
    }
 
    checked[x] = true;
    std::cout << x << ' ';
    for (int i = 0; i < versus[x].size(); i++)
    {
        dfs(versus[x][i]);
    }
}
 
int main()
{
    versus[1].push_back(2);
    versus[2].push_back(1);
 
    versus[1].push_back(3);
    versus[3].push_back(1);
 
    versus[2].push_back(4);
    versus[4].push_back(2);
 
    versus[2].push_back(5);
    versus[5].push_back(2);
 
    versus[3].push_back(6);
    versus[6].push_back(3);
 
    versus[3].push_back(7);
    versus[7].push_back(3);
 
    versus[4].push_back(5);
    versus[5].push_back(4);
 
    versus[6].push_back(7);
    versus[7].push_back(6);
 
    dfs(1);
    return 0;
}

 

사실 공부는 한참 전에 했던 것이었지만.. 강의를 듣고 도저히 코드를 이해를 할 엄두가 나지 않아, 코드로 실제로 옮기는 것은 오랫동안 미뤄두고 있었다.

물론 오늘 코드도 따라 친 것을 내 방식대로 조금 수정한 것에 불과하다곤 하지만.. 이해하면서 따라치며, 그래프 관련 문제도 드디어 풀기 시작할 수 있겠다는 용기(?)가 약간이나마 생겼다.

너무 의지박약인 것 같아 나 자신에게 미안해지는 오늘 밤이다.

 

그러나 이런 느린 한 발자국씩이라도 조금씩 걷다보면 나중에 시작하는 것보단 더 나을 것이다.

스스로에게 그런 위안을 하며 이번 포스팅을 마친다..