백준 1260 - DFS와 BFS

각 정점들의 방문 여부를 확인하는 배열 visited를 사용함

인접 행렬로 그래프 구현 (bool형 배열로 연결되었는지 확인함)

양방향 간선이라서 두 정점 모두 연결되어 있다고 구현

DFS와 BFS 둘 다 방문하지 않았고 연결되어 있다면 DFS/BFS하도록 함

DFS는 재귀 함수로 구현

BFS는 queue로 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

#define MAX_VERTICES 10000

bool arr[1001][1001] = { false }; //연결되었는지 확인하는 배열
bool dfsVisited[1001] = { false }; //dfs와 bfs에서 사용할 정점 방문 여부 배열
bool bfsVisited[1001] = { false };


int N, M, V;

void DFS(int v) { //시작할 위치, 함수 내에서 출력함
    dfsVisited[v] = true;

    printf("%d ", v);

    for (int i = 1; i <= N; i++) {
        if (arr[v][i] && !dfsVisited[i]) { //현재 정점과 연결되어 있고 방문한 적 없다면
            DFS(i);
        }
    }

}

void BFS(int v) { //queue 사용해야 함
    queue<int> q;

    bfsVisited[v] = true;
    q.push(v); //맨 앞에 현재 정점 넣어줌
    printf("%d ", v);

    while (!q.empty()) { //q가 비면 종료
        v = q.front();
        q.pop(); //현재 정점은 pop해줌

        for (int i = 1; i <= N; i++) {
            if (arr[v][i] && !bfsVisited[i]) {
                q.push(i); //맨 앞에 연결된 정점 넣어줌
                bfsVisited[i] = true;
                printf("%d ", i);
            }
        }
    }
}


int main() {

    int i;
    int u, v;
    
    scanf("%d %d %d", &N, &M, &V);


    for (i = 0; i < M; i++) { //정점 입력받기
        scanf("%d %d", &u, &v);
        arr[u][v] = true;
        arr[v][u] = true;
    }

    DFS(V);
    printf("\n");

    BFS(V);

    return 0;
}