백준(BAEKJOOB) 1260번 DFS와 BFS // c++언어

 

문제

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

입력

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

출력

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

---

이 문제를 풀기위해 너비 우선 탐색과 깊이 우선 탐색을 공부하였다.

 

 먼저 정점의 개수, 간선의 개수, 정점의 번호, 인접 그래프 등 기초적인 틀을

잡아준다.

int n, m, v;
// n=정점갯수(몇개의 노드가있는지)
// m=간선의 갯수(몇개가 연결되어있는지 ex<1 3, 1 4  이러면 두개>)
// v=정점의 번호 (시작 위치)

bool vis[1001]; //방문 했는지 안했는지
int map[1001][1001]; //인접 그래프를 나타내는 map

void reset() { //정렬후 초기화 시킴
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
}

정렬후 초기화를 적은 이유는 main에서 호출할 때 값이 섞이지 않기 위해서 이다.

 

 

먼저 bfs 알고리즘을 만들어 준다.

자세한 설명은 주석을 달아 뒀다.

void bfs(int start) {
    queue<int>queue; //큐 구현
    queue.push(start); //큐 를 시작할 숫자
    vis[start] = true; //시작할 숫자 방문 처리 

    cout << start << ' '; //시작 숫자 v 먼저 나옴
    while (!queue.empty()) { //큐가 안비었을때까지 반복
        int x = queue.front(); //x를 맨앞 숫자로 해줌
        queue.pop();
        //그런후 지워준다
        //(지웠다고 해서 앞에 x가 저장되어있는 값이 없어지지는 않는다)
        for (int i = 1; i <= n; i++) { //노드 갯수만큼 반복
            if (map[x][i] == 1 && vis[i] == 0) {
                //정점을 연결 시키고 ,방문하지 않았을때
                queue.push(i); //i를 push해줌
                vis[i] = true; //그런후 방문처리
                cout << i << ' '; //i출력
            }
        }
    }
}

 

 

dfs 에 대한 설명 

재귀 함수로 만들어 보았다. (스택을 이용해도 됨)

void dfs(int x) {
    vis[x] = true; //처음 숫자 방문처리
    cout << x << ' '; //처음 숫자 출력

    for (int i = 1; i <= n; i++) { // 노드개수 만큼 반복
        if (map[x][i] == 1 && vis[i] == 0) { //정점이 연결되어있고 방문하지않았을때
            dfs(i); //i넣고 다시호출
        }
    }

}

 

 

1을 해준 이유는 정점이 연결되어 있다는 것을 알려주기 위해서 1로 하였습니다.

int main(void) {
    cin >> n >> m >> v;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1; // 인접해 있다는것을 알려주기 위해
        map[b][a] = 1; // 인접해 있다는것을 알려주기 위해
    }

    reset();
    dfs(v);


    cout << '\n';

    reset();
    bfs(v);




    return 0;
}

 

 

총 코드

---

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

using namespace std;



int n, m, v;
// n=정점갯수(몇개의 노드가있는지)
// m=간선의 갯수(몇개가 연결되어있는지 ex<1 3, 1 4  이러면 두개>)
// v=정점의 번호 (시작 위치)

bool vis[1001]; //방문 했는지 안했는지
int map[1001][1001]; //인접 그래프를 나타내는 map

void reset() { //정렬후 초기화 시킴
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
}

void bfs(int start) {
    queue<int>queue; //큐 구현
    queue.push(start); //큐 를 시작할 숫자
    vis[start] = true; //시작할 숫자 방문 처리 

    cout << start << ' '; //시작 숫자 v 먼저 나옴
    while (!queue.empty()) { //큐가 비었지 않았을때 
        int x = queue.front(); //x를 맨앞 숫자로 해줌
        queue.pop();
        //그런후 지워준다
        //(지웠다고 해서 앞에 x가 저장되어있는 값이 없어지지는 않는다)
        for (int i = 1; i <= n; i++) { //노드 갯수만큼 반복
            if (map[x][i] == 1 && vis[i] == 0) {
                //정점을 연결 시키고 ,방문하지 않았을때
                queue.push(i); //i를 push해줌
                vis[i] = true; //그런후 방문처리
                cout << i << ' '; //i출력
            }
        }
    }
}


void dfs(int x) {
    vis[x] = true; //처음 숫자 방문처리
    cout << x << ' '; //처음 숫자 출력

    for (int i = 1; i <= n; i++) { // 노드개수 만큼 반복
        if (map[x][i] == 1 && vis[i] == 0) { //정점이 연결되어있고 방문하지않았을때
            dfs(i); //i넣고 다시호출
        }
    }

}


int main(void) {
    cin >> n >> m >> v;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1; // 인접해 있다는것을 알려주기 위해
        map[b][a] = 1; // 인접해 있다는것을 알려주기 위해
    }

    reset();
    dfs(v);


    cout << '\n';

    reset();
    bfs(v);




    return 0;
}