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

🖨 입출력

---

• 입력: N(정점의 개수), M(간선의 개수), V(처음 방문할 번호), 서로 연결된 번호쌍

• 출력: DFS 방문 순서, BFS 방문 순서

 

 

💻 C++ 제출코드

---

#include <bits/stdc++.h>

using namespace std;

void DFS(int start, deque<int> *graph, bool *check, deque<int> *DFS_result){
    stack<int> s;
    check[start] = true;
    s.push(start);
    (*DFS_result).push_back(start);

    while(!s.empty()){
        int current = s.top(); 
        s.pop(); 
        for(int next: graph[current]){
            if(check[next] == false){
                s.push(current);
                s.push(next); 
                check[next] = true;
                (*DFS_result).push_back(next);
                break;
            }
        }

    }
}
void BFS(int start, deque<int> *graph, bool *check, deque<int> *BFS_result){
    queue<int> q;
    check[start] = true;
    q.push(start);
    
    while(!q.empty()){
        int front = q.front(); 
        (*BFS_result).push_back(front);
        q.pop();
        for(int num: graph[front]){
            if(check[num] == false){
                q.push(num);
                check[num] = true;
            }
        }
    }
}

int main(){
    int N, M, V; //N: 정점의 수, M: 간선의 수, V: 시작할 정점의 번호

    scanf("%d %d %d", &N, &M, &V); 

    deque<int> graph[N];
    deque<int> DFS_result;
    deque<int> BFS_result;
    bool DFS_check[N];
    bool BFS_check[N];
    fill(DFS_check, DFS_check+N, false);
    fill(BFS_check, BFS_check+N, false);

    for(int i=0; i<M; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    for(int i=0; i<N; i++) sort(graph[i].begin(), graph[i].end());

    DFS(V-1, graph, DFS_check, &DFS_result);
    BFS(V-1, graph, BFS_check, &BFS_result);

    for(int i: DFS_result) printf("%d ", i+1);
    printf("\n");
    for(int i: BFS_result) printf("%d ", i+1);

}

 

 

 

📝 문제풀이 과정: DFS & BFS 구현

---

#include <iostream>
#include <stdio.h>
#include <deque>
#include <queue>
#include <algorithm>
#include <stack>

using namespace std;

void DFS(int start, deque<int> *graph, bool *check, deque<int> *DFS_result){
    stack<int> s;
    check[start] = true;
    s.push(start);
    printf("[+] %d VISITED\n", start);

    while(!s.empty()){
        int front = s.top(); 
        s.pop(); printf("[+] POPED %d\n", front);
        (*DFS_result).push_back(front);
        for(int num: graph[front]){
            if(check[num] == false){
                s.push(num); 
                check[num] = true;
                printf("[+] %d VISITED\n", num);
            }
        }

    }
}
void BFS(int start, deque<int> *graph, bool *check, deque<int> *BFS_result){
    queue<int> q;
    check[start] = true;
    q.push(start);
    printf("[+] %d VISITED\n", start);
    
    while(!q.empty()){
        int front = q.front(); printf("[+] POPED %d\n", front);
        (*BFS_result).push_back(front);
        q.pop();
        for(int num: graph[front]){
            if(check[num] == false){
                q.push(num);
                check[num] = true;
                printf("[+] %d VISITED\n", num);
            }
        }
    }
}

int main(){
    int N, M, V; //N: 정점의 수, M: 간선의 수, V: 시작할 정점의 번호

    scanf("%d %d %d", &N, &M, &V); 

    deque<int> graph[N];
    deque<int> DFS_result;
    deque<int> BFS_result;
    bool DFS_check[N];
    bool BFS_check[N];
    
    fill(DFS_check, DFS_check+N, false);
    fill(BFS_check, BFS_check+N, false);

    for(int i=0; i<M; i++){
        int u,v;
        scanf("%d %d", &u, &v);
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }

    for(int i=0; i<N; i++) sort(graph[i].begin(), graph[i].end());

    DFS(V-1, graph, DFS_check, &DFS_result);
    BFS(V-1, graph, BFS_check, &BFS_result);

    printf("RESULT OF DFS: ");
    for(int i: DFS_result) printf("%d ", i);

    printf("\nRESULT OF BFS: ");
    for(int i: BFS_result) printf("%d ", i);

}

1. DFS 구현

• recursive와 stack으로 구현할 수 있다.

• 백준 2606: 바이러스 문제에서 recursive로 구현했어서, 이번에는 stack으로 구현해봤다.

• stack의 경우, top에서만 넣고 꺼낼 수 있으므로 가장 마지막에 넣은 원소부터 pop할 수 있다.

• 처음 시작하는 번호부터 방문 체크를 해주고, stack에 넣는다. 다시 이 원소를 pop을 해서 해당 번호에 연결된 원소들를 stack에 넣는다. 

• 이미 방문한 원소는 stack에 넣지 않는다.

• 첫 번째 원소에 연결된 다른 원소도 방문해야 하므로, 다시 첫 번째 원소를 stack에 넣은 후, 방문한 첫 번째 원소에 연결된 원소를 stack에 넣는다.

• 다음으로는 top에 있는 아까 넣었던 원소를 pop한 후, top의 원소를 stack에 넣은 후 이 top 원소에 연결된 원소를 stack에 넣는다. 

• 위의 과정을 stack이 empty가 될 때까지 반복한 후 종료된다.

• stack에서 pop한 순서가 DFS에서의 방문순서이다.

• DFS의 경우, result에 넣을 때 BFS나 기존 recursive 구현 때처럼 while문 초반에 넣으면 맨 처음 원소가 안 들어가서 start 원소를 push해주는 것을 while문 전에 넣어줬다.

2. BFS 구현

• queue로 구현 (FIFO)

• queue의 경우, front를 pop하고 front에 연결된 원소을 queue 뒤에 차례로 넣는 과정을 empty가 아닐 때까지 반복한다.

• 이미 방문한 원소는 queue에 넣지 않는다.

• queue에서 원소를 빼는 순서가 방문 순서이다.

• 처음 방문하는 번호는 0부터 시작하므로 V-1로 줬다.

 

 

👏 결과

---