백준 1260번 DFS와 BFS

문제 링크입니다: https://www.acmicpc.net/problem/1260

자료구조 시간에서 다루었던 BFS(Breadth First Search)와 DFS(Depth First Search)를 복습할 겸 풀어봤던 문제였습니다.

실제로 BFS와 DFS는 자주 다루어지는 알고리즘이기 때문에 익숙해져있어야 하는 알고리즘입니다.

BFS는 방문한 노드로부터 아직 방문하지 않은 인접한 모든 노드를 큐에 추가하는 방식으로 너비 우선 탐색을 진행하고 DFS는 방문한 노드에서 아직 방문하지 않은 인접한 노드로 옮겨가는 식으로 깊이 우선 탐색을 진행합니다.

#include <iostream>

#include <queue>

#include <cstring>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, M, V;

int adjacent[MAX][MAX];

bool visited[MAX];

queue<int> q;

 

void DFS(int idx)

{

        cout << idx << " ";

 

        for(int i=1; i<=N; i++)

                 if (adjacent[idx][i] && !visited[i])

                 {

                         visited[i] = 1;

                         //인접한 노드에 대해서 또 다시 DFS

                         DFS(i);

                 }

}

 

void BFS(int idx)

{

        q.push(idx);

        visited[idx] = 1;

 

        while (!q.empty())

        {

                 idx = q.front();

                 q.pop();

 

                 cout << idx << " ";

 

                 //BFS는 해당 노드에 인접한 노드들을 모두 추가한 뒤 BFS 진행

                 for(int i=1; i<=N; i++)

                         if (adjacent[idx][i] && !visited[i])

                         {

                                 visited[i] = 1;

                                 q.push(i);

                         }

        }

}

 

int main(void)

{

        cin >> N >> M >> V;

 

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

        {

                 int from, to;

                 cin >> from >> to;

                 adjacent[from][to] = 1;

                 adjacent[to][from] = 1;

        }

 

        visited[V] = 1; //V에서 시작하므로

        DFS(V);

        cout << endl;

 

        memset(visited, false, sizeof(visited));

        BFS(V);

        cout << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~