[백준/C++] 1260번 DFS와 BFS

문제링크

1260번 DFS와 BFS

 

 

DFS와 BFS의 개념 문제

DFS는 재귀를 통해 구현(스택을 통해서도 구현 가능), BFS는 큐를 통해 구현한다.

DFS와 BFS 구현의 핵심은 방문처리

DFS는 완전탐색, BFS는 최단 경로 혹은 임의의 경로 계산에 많이 쓰인다.

 

 

 

제출 코드

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

       
int N, M, V;
int arr[1001][1001];    // 인접행렬
int visited[1001];      // 방문기록(bool을 써줘도 됨)

void DFS(int V);
void BFS(int V);

int main() {

    int a, b;

    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> a >> b;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }

    DFS(V);

    cout << "\n";
    memset(visited, 0, sizeof(visited));	// 방문 배열 0으로 초기화

    BFS(V);

    return 0;
}

void DFS(int V)
{
    visited[V] = 1;     // 시작점 방문한 노드 기록
    cout << V << " ";

    for (int i = 1; i <= N; i++)
    {
        if (arr[V][i] == 1 && visited[i] == 0)
        {
            DFS(i);
        }
        if (i == N)
        {
            return;
        }
    }
}

void BFS(int V)
{
    queue<int> q;
    q.push(V);          // 시작노드를 큐에 넣음

    while (!q.empty())
    {
        int next = q.front();   // 큐 맨 앞의 값 방문
        visited[next] = 1;      // 방문노드 기록
        cout << next << " ";
        q.pop();                // 큐에서 뺌

        // 방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited[i] == 0)
            {
                q.push(i);  // 큐에 넣어줌
                visited[i] = 1; // i점 방문기록하여 중복 방지
            }
        }
    }
}