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

백준 1260번 "DFS와 BFS" 문제 풀이입니다.

 

해당 문제 링크

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

문제

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

입력

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

 

출력

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

 

[예제 입력 1]

4 5 1 (정점 갯수, 간선 갯수, 시작 정점)
1 2
1 3
1 4
2 4
3 4

 

[예제 출력 1]

1 2 4 3 (DFS 순서)
1 2 3 4 (BFS 순서)

 

[예제 입력 2]

5 5 3
5 4
5 2
1 2
3 4
3 1

 

[예제 출력 2]

3 1 2 5 4
3 1 4 2 5

 

[예제 입력 3]

1000 1 1000
999 1000

 

[예제 출력 3]

1000 999 
1000 999

---

개인적인 풀이

 

1. 먼저 필요한 변수, 벡터 등을 선언해 줍니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 1001

using namespace std;

// 정점 갯수, 간선 갯수, 시작 정점
int N, M, V;
// 방문 여부
int visited[MAX];

vector<int> graph[MAX];

 

2. 입력값을 처리해 주고, graph 벡터를 각각 정점들에 대해서 오름차순 정렬시켜 줍니다.

void input() {
    cin >> N >> M >> V;
	
    for (int m=0; m<M; ++m) {
        int p,q;
        cin >> p >> q;
        
        // 각 정점마다 연결된 정점들을 각 벡터에 저장
        graph[p].push_back(q);
        graph[q].push_back(p);
    }
    
    for (int n=1; n<=N; ++n) {
        // 벡터를 오름차순으로 정렬
        sort(graph[n].begin(), graph[n].end(), less<int>());
    }
}

 

3. 방문 여부 판단하는 배열은 dfs가 끝난 뒤, 초기화해야 합니다.

void init() {
    for (int n=1; n<=N; ++n) {
        // 방문하지 않은 상태(false)로 만들기
        visited[n] = 0;
    }
}

 

4. 파라미터를 시작 정점으로 갖는 dfs 함수를 작성합니다.

void dfs(int v) {
    cout << v << " ";

    // 시작 정점에 연결된 정점들 중에서
    // 방문하지 않은 정점이 있으면 방문! (작은 숫자부터)
    for (int n=0; n<graph[v].size(); ++n) {
        int nv = graph[v][n];
        if (!visited[nv]) {
            // 방문 표시하고, dfs 이동
            visited[nv] = 1;
            dfs(nv);
        }
    }
}

 

5. 파라미터를 시작 정점으로 갖는 bfs 함수도 작성합니다.

void bfs(int v) {
    queue<int> que;
    que.push(v);
    
    // queue가 비어있지 않으면 계속 진행
    while (!que.empty()) {
        // 가장 앞에 있는 정점 pop
        int f = que.front();
        cout << f << " ";
        que.pop();
        
        // nv에 연결되어 있는 방문하지 않은 정점들 다 que에 넣기
        for (int n=0; n<graph[f].size(); ++n) {
            int nv = graph[f][n];
            if (!visited[nv]) {
                que.push(nv);
                // 방문 표시
                visited[nv] = 1;
            }      
        }
    }
}

 

6. 마지막으로 main 함수를 작성!

int main(void) {
    input();

    visited[V] = 1;
    dfs(V);
    cout << endl;

    init();
    visited[V] = 1;
    bfs(V);
    cout << endl;
    return 0;
}

 

---

 

[전체 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 1001

using namespace std;

// 정점 갯수, 간선 갯수, 시작 정점
int N, M, V;
// 방문 여부
int visited[MAX];

vector<int> graph[MAX];

void input() {
    cin >> N >> M >> V;
	
    for (int m=0; m<M; ++m) {
        int p,q;
        cin >> p >> q;
        
        // 각 정점마다 연결된 정점들을 각 벡터에 저장
        graph[p].push_back(q);
        graph[q].push_back(p);
    }

    for (int n=1; n<=N; ++n) {
        // 벡터를 오름차순으로 정렬
        sort(graph[n].begin(), graph[n].end(), less<int>());
    }
}

void init() {
    for (int n=1; n<=N; ++n) {
        // 방문하지 않은 상태(false)로 만들기
        visited[n] = 0;
    }
}

void dfs(int v) {
    cout << v << " ";

    // 시작 정점에 연결된 정점들 중에서
    // 방문하지 않은 정점이 있으면 방문! (작은 숫자부터)
    for (int n=0; n<graph[v].size(); ++n) {
        int nv = graph[v][n];
        if (!visited[nv]) {
            // 방문 표시하고, dfs 이동
            visited[nv] = 1;
            dfs(nv);
        }
    }
}

void bfs(int v) {
    queue<int> que;
    que.push(v);
    
    // queue가 비어있지 않으면 계속 진행
    while (!que.empty()) {
        // 가장 앞에 있는 정점 pop
        int nv = que.front();
        cout << nv << " ";
        que.pop();
        
        // nv에 연결되어 있는 방문하지 않은 정점들 다 que에 넣기
        for (int n=0; n<graph[nv].size(); ++n) {
            int nnv = graph[nv][n];
            if (!visited[nnv]) {
                que.push(nnv);
                // 방문 표시
                visited[nnv] = 1;
            }      
        }
    }
}

int main(void) {
    input();

    visited[V] = 1;
    dfs(V);
    cout << endl;

    init();
    visited[V] = 1;
    bfs(V);
    cout << endl;
    return 0;
}