[C++] 백준 온라인저지 DFS와 BFS 풀이

제목 그대로 DFS와 BFS로 그래프를 탐색한 결과를 출력하는 문제

 

---

문제의 조건

 

1. 주어진 그래프를 DFS와 BFS로 각각 탐색한 결과를 순서대로 출력하면 된다. 

 

2. 단, 방문할 수 있는 정점의 개수가 여러 개면 정점의 수가 작은 것 부터 방문한다. 

 

---

풀이 과정

 

처음에는 요즘 알고리즘을 공부하고 있는 책에 나와 있는 알고리즘을 썼는데...

(대충 엣지 좌우 저장하는 구조체 만들고

전체 그래프를 구성하는 클래스를 만든 뒤 

그렇게 만들어진 그래프 클래스를 이용해서 bfs와 dfs를 수행하는 내용

코드 길이가 A4 한 장 정도 됨)

알고 보니 모든 정점이 서로서로 연결되어 있다는 것을 전제로 한 알고리즘이라 이번 문제에는 맞지 않았습니다.

주륵 ㅠ.ㅠ

그리고 제게는 그것을 수정할 능력이 없었습니다...ㅋㅋㅋㅋㅋㅋㅋ 

그것도 모르고 몇 시간을 날렸지만 이제 알게 되었으니 다음부터는 실수를 안 할 수 있을 것이라 생각해요. 

이번 경험을 바탕으로 담에 잘 하면 되져 뭐 ㅋㅋ

 

암튼 좀 더 심플하게 그래프를 구성하고 탐색할 수 있는 풀이를 찾아 참고하여 풀었습니다. 

 

https://jaimemin.tistory.com/561

백준 1260번 DFS와 BFS

 

풀이에 참고한 블로그

 

---

 

 

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

using namespace std;

const int MAX = 1000 + 1;

int N, M, V;
//2차원 배열로 그래프 구성 
vector<vector<bool>> Graph(MAX, vector<bool>(MAX, false));

void CreateGraph(const int N, const int M)
{
    for (int i = 0; M > i; i++)
    {
        //양방향 그래프니까 양쪽 방향 모두를 true로 바꿔준다. 
        int from, to;
        cin >> from >> to;
        Graph[from][to] = true;
        Graph[to][from] = true;
    }
}

void bfs(int V)
{
    queue<int> queue;
    set<int> visited;
    queue.emplace(V);
    
    while (!queue.empty())
    {
        V = queue.front();
        queue.pop();
        
        if (visited.end() == visited.find(V))
        {
            visited.insert(V);
            cout << V << " ";
            
            for (int i = 1; N >= i; i++)
            {
                //현재 정점(V) 기준으로 방문할 수 있는 곳 큐에 저장 
                if (Graph[V][i] && visited.end() == visited.find(i))
                    queue.emplace(i);
            }
        }
    }
}

//dfs는 재귀호출이 이루어져야 해서 방문 체크용 set을 전역으로 선언 
set<int> dfsVisited;
void dfs(int V)
{
    cout << V << " ";
    
    for (int i = 1; N >= i; i++)
    {
        if (Graph[V][i] && dfsVisited.end() == dfsVisited.find(i))
        {
            //현재 정점(V)에서 방문하지 않은 정점이 남아 있다면 거기로 들어가기 
            //이 조건에 들어왔으면 해당 정점을 방문한 것이나 다름없다... 방문 set에 추가 후 재귀호출 
            dfsVisited.insert(i);
            dfs(i);
        }
            
    }
}

int main(int argc, const char * argv[])
{
    cin >> N >> M >> V;
    
    CreateGraph(N, M);
    
    //시작 정점은 방문한 상태니까 방문 set에 추가 
    dfsVisited.insert(V);
    dfs(V);
    
    cout << endl;
    
    bfs(V);
    
    return 0;
}