DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

- 출처 : www.acmicpc.net - 

 

그래프를 탐색해야하고 정점과 간선이 주어진다.

해당정보를 가지고 문제를 해결하는데 인접행렬을 사용했다.

인접행렬이란

그래프 상의 연결 관계를 이차원 배열로 나타내는 방법이다.

예제 입력 1번을 예를 들어보면

정점의 개수 : 4 이므로

오른쪽과 같은 이차원 행렬을 만들수 있다.

여기서 간선의 개수는 5이고 각각의 값이 주어진다.

(1,2), (1,3) (1,4), (2,4), (3,4) 

 

 

이 값을 행렬에 넣어보면

오른쪽과 같은 인접행렬을 만들 수 있다.

인접행렬의 장점은 구현이 쉽다.

또한 특정 노드의 연결 여부를 확인하고 싶을 때, adj[i][j]가 1 or 0의 여부만 확인하면 된다.

하지만 전체 노드의 개수가 아주 많을 경우에 간선의 개수와 관계없이 모든 노드를 다 확인해봐야 하는 단점이 있다.

(이 단점을 보완하는 것이 인접 리스트이다.)

인접행렬을 사용해서 이 문제를 풀었을때의 코드는 아래와 같다.

 

 

 

//
//  main.cpp
//  dfs_bfs
//
//  Created by 조우석 on 04/08/2019.
//  Copyright © 2019 j0dev. All rights reserved.
//

#include <iostream>
#include <queue>


using namespace std;
#define arr_len 1001
int node_num, line_num, start_num, line_start, line_end;
int adj_arr[arr_len][arr_len];
int *dfs_arr;
int *bfs_arr;

void dfs(int start_num);
void bfs(int start_num);

int main(int argc, const char * argv[]) {
    // insert code here...
    cin >> node_num >> line_num >> start_num;
    start_num = start_num-1;

   
    //인접 행렬 입력
    for (int i=0; i<line_num; i++) {
        cin >> line_start >> line_end;
        line_start = line_start-1;
        line_end = line_end-1;
        adj_arr[line_start][line_end] = 1;
        adj_arr[line_end][line_start] = 1;
    }
    
    dfs_arr = new int[node_num];
    bfs_arr = new int[node_num];

    dfs(start_num);
    bfs(start_num);

   
    delete dfs_arr;
    delete bfs_arr;
    
    return 0;
}

void dfs(int start_num){
    cout << start_num+1 << ' ' ;
    dfs_arr[start_num] = 1;
    for (int i=0; i<node_num; i++){
        if(dfs_arr[i] == 1 || adj_arr[start_num][i] == 0) {
            continue;
        } else {
            dfs(i);
        }
    }
}

void bfs(int start_num){
    cout << "\n";
    queue<int> bfs_q;
    bfs_q.push(start_num);
    bfs_arr[start_num]=1;
    while (!bfs_q.empty()) {
        start_num=bfs_q.front();
        cout << start_num+1 << ' ';
        bfs_q.pop();
        for (int i=0; i<node_num; i++){
            if(bfs_arr[i] == 1 || adj_arr[start_num][i] == 0){
                continue;
            } else {
                bfs_q.push(i);
                bfs_arr[i]=1;
            }
        }
        
    }
}

 

주어진 입력값에 맞춰 인접행렬을 만들고

각각 dfs와 bfs를 처리할 배열을 만들어준다.

 

이때 인접행렬에 대한 다차원 배열 생성 당시, 동적할당을 해주니깐, 백준문제집에서는 메모리 초과가 나서

define으로 크기를 고정해주니 해결되었다.

 

dfs와 bfs를 각각 스택과 큐를 사용하여 구현하면 쉽다.

 

---

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

- 출처 : www.acmicpc.net - 

 

그래프를 탐색해야하고 정점과 간선이 주어진다.

해당정보를 가지고 문제를 해결하는데 인접행렬을 사용했다.

인접행렬이란

그래프 상의 연결 관계를 이차원 배열로 나타내는 방법이다.

예제 입력 1번을 예를 들어보면

정점의 개수 : 4 이므로

오른쪽과 같은 이차원 행렬을 만들수 있다.

여기서 간선의 개수는 5이고 각각의 값이 주어진다.

(1,2), (1,3) (1,4), (2,4), (3,4) 

 

이 값을 행렬에 넣어보면

오른쪽과 같은 인접행렬을 만들 수 있다.

인접행렬의 장점은 구현이 쉽다.

또한 특정 노드의 연결 여부를 확인하고 싶을 때, adj[i][j]가 1 or 0의 여부만 확인하면 된다.

하지만 전체 노드의 개수가 아주 많을 경우에 간선의 개수와 관계없이 모든 노드를 다 확인해봐야 하는 단점이 있다.

(이 단점을 보완하는 것이 인접 리스트이다.)

인접행렬을 사용해서 이 문제를 풀었을때의 코드는 아래와 같다.

 

 

 

//
//  main.cpp
//  dfs_bfs
//
//  Created by 조우석 on 04/08/2019.
//  Copyright © 2019 j0dev. All rights reserved.
//

#include <iostream>
#include <queue>


using namespace std;
#define arr_len 1001
int node_num, line_num, start_num, line_start, line_end;
int adj_arr[arr_len][arr_len];
int *dfs_arr;
int *bfs_arr;

void dfs(int start_num);
void bfs(int start_num);

int main(int argc, const char * argv[]) {
    // insert code here...
    cin >> node_num >> line_num >> start_num;
    start_num = start_num-1;

   
    //인접 행렬 입력
    for (int i=0; i<line_num; i++) {
        cin >> line_start >> line_end;
        line_start = line_start-1;
        line_end = line_end-1;
        adj_arr[line_start][line_end] = 1;
        adj_arr[line_end][line_start] = 1;
    }
    
    dfs_arr = new int[node_num];
    bfs_arr = new int[node_num];

    dfs(start_num);
    bfs(start_num);

   
    delete dfs_arr;
    delete bfs_arr;
    
    return 0;
}

void dfs(int start_num){
    cout << start_num+1 << ' ' ;
    dfs_arr[start_num] = 1;
    for (int i=0; i<node_num; i++){
        if(dfs_arr[i] == 1 || adj_arr[start_num][i] == 0) {
            continue;
        } else {
            dfs(i);
        }
    }
}

void bfs(int start_num){
    cout << "\n";
    queue<int> bfs_q;
    bfs_q.push(start_num);
    bfs_arr[start_num]=1;
    while (!bfs_q.empty()) {
        start_num=bfs_q.front();
        cout << start_num+1 << ' ';
        bfs_q.pop();
        for (int i=0; i<node_num; i++){
            if(bfs_arr[i] == 1 || adj_arr[start_num][i] == 0){
                continue;
            } else {
                bfs_q.push(i);
                bfs_arr[i]=1;
            }
        }
        
    }
}

 

주어진 입력값에 맞춰 인접행렬을 만들고

각각 dfs와 bfs를 처리할 배열을 만들어준다.

 

이때 인접행렬에 대한 다차원 배열 생성 당시, 동적할당을 해주니깐, 백준문제집에서는 메모리 초과가 나서

define으로 크기를 고정해주니 해결되었다.

 

dfs와 bfs를 각각 스택과 큐를 사용하여 구현하면 쉽다.