[백준 | C++] DFS와 BFS

틀린 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int vertex_cnt, edge_cnt, start_vertex_num;
vector<int> adj_list[1001]; //1001 -> 'N'이 1~1000 이므로 1000번째 인덱스에 접근
bool visit_dfs[1001]; //bool -> 이미 방문한 곳인지 확인
bool visit_bfs[1001];

void dfs(int cur_vertex_num) {
    cout << cur_vertex_num << " ";  //해당 번호 출력
    visit_dfs[cur_vertex_num] = true;  //방문한 정점 기록
    for (int vertex : adj_list[cur_vertex_num]) {  //해당 정점이 방문할 수 있는 정점들 중에서 방문하지 않은 정점으로 진입
        if (!visit_dfs[vertex]) {
            dfs(vertex);
        }
    }
}

void bfs(int strat_vertex_num) {
    queue<int>q;
    q.push(start_vertex_num);  //매개변수로 받은 시작점을 큐에 삽입
    visit_bfs[start_vertex_num] = true;  //방문한 정점 기록
    while(!q.empty()) {
        int cur_vertex_num = q.front();  //큐의 front에 현재 정점 선언
        q.pop();
        cout << cur_vertex_num << " ";  //큐의 front 출력
        for (int vertex : adj_list[cur_vertex_num]) {
            if (!visit_bfs[vertex]) {
                visit_bfs[vertex] = true;
                q.push(vertex);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> vertex_cnt >> edge_cnt >> start_vertex_num;
    
    for (int i = 1; i <= edge_cnt; i++) {  //간선이 연결하는 두 정점의 번호 입력받기
        int source, dest;
        cin >> source, dest;
        adj_list[source].push_back(dest);
        adj_list[dest].push_back(source);
    }
    
    for (int i = 1; i <= vertex_cnt; i++) {
        sort(adj_list[i].begin(), adj_list[i].end()); //sort알고리즘 -> 각 정점들의 인접 리스트들을 오름차순으로 정렬
    }
    
    dfs(start_vertex_num);
    cout << '\n';
    bfs(start_vertex_num);
    
    return 0;
}

다시 한 풀이

입력으로 주어지는 간선은 양방향이다. -> 인접행렬 사용

인접행렬
배열의 인덱스 [i,j]에서 i와 j가 서로 바뀌어도 값이 동일한 행렬

#include <iostream>
#include<queue>
using namespace std;
#define MAX_VALUE 1001 //N이 1~1000이므로

int N, M, V;
int mat[MAX_VALUE][MAX_VALUE];  //인접행렬 배열 선언
int visit[MAX_VALUE];

void dfs(int v) {
    cout << v << ' ';
    visit[v] = 1;  //방문한 노드를 visit 0에서 1로 변경
    for(int i=1; i<=N; i++) {
        if(visit[i] == 1 || mat[v][i] == 0)
            continue;
        dfs(i);
    }
}

void bfs(int v) {
    queue<int> q;
    q.push(v);
    visit[v] = 0;  //방문한 노드를 visit 1에서 0으로 변경
    while(!q.empty()) {
        v = q.front();
        cout << q.front() << ' ';
        q.pop();
        for (int i=1; i<=N; i++) {
            if(visit[i] == 0 || mat[v][i] == 0)
                continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}

int main() {
    int x, y;
    cin >> N >> M >> V;
    for (int i=0; i<M; i++) {
        cin >> x >> y;
        mat[x][y] = mat[y][x] = 1;  //인접행렬 표시
    }
    dfs(V);
    cout << '\n';
    bfs(V);
    return 0;
}