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

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

그래프에서의 DFS와 BFS를 연습할 수 있는 좋은 문제입니다. 인접 행렬 혹은 인접 리스트를 이용해서 그래프를 만들 수 있는데, 저는 인접 리스트를 이용했습니다.

 

※ 인접 행렬과 인접 리스트의 차이점이 궁금했었는데 잘 설명한 블로그 글이 있어 주소를 남겨봅니다!

seohyun0120.tistory.com/entry/C-BFS%EC%99%80-DFS-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91%EB%A6%AC%EC%8A%A4%ED%8A%B8

(C++) BFS와 DFS, 인접행렬과 인접리스트

 

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

int n, m, v;
vector<int> graph[1001];
bool visit[1001];

void BFS(int idx) {
    memset(visit, false, sizeof(visit));
    queue<int> q;
    q.push(idx);
    visit[idx] = true;
    
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        cout<<now<<" ";
        
        for(int i = 0; i < graph[now].size(); i++) {
            int next = graph[now][i];
            if(!visit[next]) {
                q.push(next);
                visit[next] = true;
            }
        }
    }
}

void DFS(int idx) {
    visit[idx] = true;
    cout<<idx<<" ";
    
    for(int i = 0; i < graph[idx].size(); i++) {
        int next = graph[idx][i];
        if(!visit[next]) DFS(next);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>v;
    while(m--) {
        int x, y;
        cin>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    
    for(int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end()); // 인접리스트 오름차순 정렬
    }
    
    DFS(v);
    cout<<"\n";
    BFS(v);
}