1260

1260번: DFS와 BFS

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

www.acmicpc.net

DFS와 BFS 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

82797

26581

15511

30.943%

문제

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

입력

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

1 2 4 3 1 2 3 4

예제 입력 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

출처

문제를 만든 사람: author5
데이터를 추가한 사람: djm03178 doju
어색한 표현을 찾은 사람: doju
빠진 조건을 찾은 사람: pumpyboom

<개인 풀이>

개념을 적용하여 구현

dfs와 bfs 인접리스트를 활용한 재귀

bfs는 큐를 이용하여 막히면 다음 정점으로 이동

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
 
void dfs(int n);
void bfs(int n);
vector<int> p[1001];
bool check[1001] = { 0, };
queue<int> q;
int main(void)
{
    
    int n, m, v;
 
    // n 정점 갯수, m 간선 갯수
    // v 시작 정점 번호 v
    scanf("%d %d %d", &n, &m, &v);
 
 
    int from = 0, to = 0;
    for (unsigned short i = 0; i < m; ++i)
    {
        scanf("%d %d", &from, &to);
        p[from].push_back(to);
        p[to].push_back(from);
 
    }
    
    //정점 번호가 작은것을 먼저 방문, 오름차순 정렬
    for (unsigned short i = 0; i < n; ++i)
    {
        sort(p[i].begin(), p[i].end());
    }
 
    dfs(v);
    memset(check, false, sizeof(check));
    printf("\n");
    bfs(v);
    return 0;
}
void dfs(int n)
{
    int temp = 0;
    if (check[n]){}
    else
    {
        check[n] = true;
        printf("%d ", n);
        for (unsigned short i = 0; i < p[n].size(); ++i)
        {
            temp = p[n][i];
            dfs(temp);
        }
    }
}
 
void bfs(int n)
{
    if (check[n]){}
    else
    {
        check[n] = true;
        printf("%d ", n);
    }
    for (unsigned short i = 0; i < p[n].size(); ++i)
    {
        if (check[p[n][i]])
        {
            
        }
        else
        {
            check[p[n][i]] = true;
            q.push(p[n][i]);
            printf("%d ", p[n][i]);
        }
    }// n정점으로 부터 연결된 간선들을 q에 저장
    
    if (q.empty())
    {
 
    }
    else
    {
        int temp = q.front();
        q.pop();
        bfs(temp);
    }
    
}
 

cs

저작자표시 (새창열림)