[c++] 백준 1260번 : BFS 와 DFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

함수/ 변수 설명

graph - 노드와 간선으로 이루어진 그래프를 담을 2차원 벡터

visited - 노드에 방문 했는지 채크하는 bool 형 벡터

N, M, V - 입력받을 변수

 

dfs - DFS 탐색을 할 함수

     now - 현재 위치

 

bfs - BFS 탐색을 할 함수

     q - 탐색할 노드들을 정렬

     start - 탐색 시작 지점

     next - 다음 탐색 노드

---

 

그래프 구현방식 차이

	시간복잡도(dfs, bfs)	공간복잡도
인접행렬(graph)	N²	N²
인접리스트(노드수 n 간선수 m)	N + M	M

---

완성 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
int N, M, V;

void dfs(int now) {

    cout << now << ' ';
    visited[now] = true;

    //graph 의 now 번째에 탐색하지 않는 노드가 있는지 확인하고 함수 재귀호출
    for (int i : graph[now]) {
        if (!visited[i]) {
            dfs(i);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);      //start 로 시작
    visited[start] = true;

    while (!q.empty()) {
        int now = q.front();  //현재 위치를 큐의 가장 앞에있는 값으로 설정
        q.pop();              //큐 비우기
        cout << now << " ";
        for (int next : graph[now]) {
            //다음 노드가 탐색이 되어있지 않다면 탐색하기
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }

}

int main() {
    cin >> N >> M >> V;

    //1 부터 탐색을 할것이므로 N + 1 로 크기를 정해준다(0부터 한다면 N 으로 크기를 정한다)
    graph.resize(N + 1);
    visited.resize(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;

        //"양방향" 그래프 생성
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(V);

    cout << "\n";
    fill(visited.begin(),visited.end(),false);  //visited 배열 초기화

    bfs(V);

    return 0;
}

---

etc...

main 함수 인접행렬 코드

graph.resize(N,vector<int>(n + 1));
visited.resize(N + 1);

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

 

dfs 함수에서 방문하지 않은 노드를 탐색하는 for 문은 아래 코드들로 바꿀 수 있다.

for(int i=1; i <= N; i++){
     if(graph[now][i] != 0 && !visited[i]){
         dfs(i);
     }
 }

for(int i=0; i < graph[now].size(); i++){
     if(!visited[graph[now][i]]){
         dfs(graph[now][i]);
     }
}

 

6/20 다시풀기