본문 바로가기

알고리즘

[백준알고] [1260]:DFS와 BFS

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

실수로 임시 저장 안해서 글 거의 다쓴거 다시 새로씁니다.

오늘의 교훈 : 임시저장을 생활화 하자...

 

이 문제는 DFS와 BFS의 차이점을 알 수 있는 좋은 문제인거 같습니다.

그럼 포스팅 시작합니다!!!


시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 28767 8994 5445 29.607%

문제

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

입력

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

출력

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

예제 입력 

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

예제 출력 

1 2 4 3
1 2 3 4

 

 

 

 

 

 

 

 

 

음... 먼저 BFS와 DFS의 차이점에 대해서 알아보겠습니다.

 

DFS(Depth-first Search)  - 깊이우선탐색, 말그대로 그래프에서 가장 최상위 노드부터 하위노드까지 제일깊게 탐색하고, 다시 위로올라와서 깊게 깊게 탐색하는 방법입니다.

BFS(Breadth-first Search) - 너비우선탐색, 말 그대로 그래프에서 가장 최상위 노드부터 다음 차수(degree)를 모두 탐색하고, 그 다음차수를 모두 너비너비하게 탐색 하는 방법입니다.

 

 

위 그림을 보면 BFS와 DFS의 차이점을 알 수 있습니다.  (마우스 고장나서 그리느라 애먹음......ㅠ)

 

 

그럼, 다시 문제로 돌아가서 Test Case대로 숫자를 입력받으면 어떤 그래프가 나오는지 보겠습니다.

 

 

노드와 간선을 입력받고 연결시킨 그래프입니다. Test Case 상으로는 노드 1부터 시작하게 됩니다.

숫자가 낮은순부터 높은순대로 탐색하는 조건이 있습니다. 이를 토대로 DFS와 BFS의 탐색 결과를 보면 아래와 같습니다.

DFS : 1 - 2 - 4 - 3

BFS : 1 - 2 - 3 - 4

 

이 문제를 풀기위해서 숫자들끼리 연결된것을 어떤식으로 표현하고,코딩할 것인가를 고민하다가 인접행렬을 생각했습니다. 인접행렬이란 배열의 인덱스 i,j가 서로 바뀌어도 같은 1의 값을 가진것입니다...음 예를들어

 

이런식으로 표현된것도 인접행렬입니다. N크기의 배열에서 1행 2열 과 2행 1열의 수가 1로 같고, 2행 3열 과 3행 2열의                    수가 1로 같기 때문이죠

인접행렬을 통해 그래프가 양방향으로 연결됨을 표현할 수 있습니다. 그럼 문제의 TestCase를 토대로 인접행렬을 표현해 보겠습니다.

 

 이 그림을 통해서 Test Case에서 노드를 양방향으로 연결한 간선을 표현할 수 있습니다.

 

그럼 인접행렬까지 알게 되었으니, 완성된 코드를 통해서 다음 설명을 진행하겠습니다.

 

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
#include<iostream>
#include<queue>
using namespace std;
 
#define MAX_VALUE 1001            //'N이 1~1000 이므로 1000번째 인덱스에 접근 -> 크기 1001까지 선언
int N, M, V;                    //노드 개수, 간선 개수, 시작할 노드 번호
int mat[MAX_VALUE][MAX_VALUE];    //인접행렬 배열 선언
int visit[MAX_VALUE];            //visit 배열 default 는 0으로. . . 
 
void dfs(int v) {
    
    cout << v << ' ' ;
    visit[v] = 1;            //방문한 노드를 visit 0에서 1로 변경
    for(int i=1; i<=N; i++) {
        if(visit[i] == 1 || mat[v][i] == 0)     
            continue;
        dfs(i);                //dfs에서 재귀를 사용
    }
}
 
void bfs(int v) {
    queue<int> q;            //bfs에서는 q를사용
    q.push(v);
    visit[v] = 0;            //방문한 노드를 visit 1에서 0으로 변경
    while(!q.empty()) {
        v = q.front();
        cout << q.front() << ' ';
        q.pop();
        for(int i=1; i<=N; i++) {
            if(visit[i] == 0 || mat[v][i] == 0)
                continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}
 
int main() {
    int x, y;.
    cin >> N >> M >> V;            //N은 노드개수, M은 간선의개수, V는 처음 위치의 기준이 되는 노드
    for(int i=0; i<M; i++) {    //간선의 개수만큼 서로 이어줄 x와 y노드를 입력받습니다.
        cin >> x >> y;            
        mat[x][y] = mat[y][x] = 1;    //인접행렬 표시
    }
    dfs(V);            
    cout << '\n';
    bfs(V);
    return 0;
}

cs

 

제가 완성한 코드입니다.

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
int main() {
    int x, y;.
    cin >> N >> M >> V;            //N은 노드개수, M은 간선의개수, V는 처음 위치의 기준이 되는 노드
    for(int i=0; i<M; i++) {    //간선의 개수만큼 서로 이어줄 x와 y노드를 입력받습니다.
        cin >> x >> y;            
        mat[x][y] = mat[y][x] = 1;    //인접행렬 표시
    }
    dfs(V);            
    cout << '\n';
    bfs(V);
    return 0;
}
cs

 

일단 메인함수를 보게되면, N, M, V를 입력받고, 서로 양방향으로 연결한 노드를 x,y를통해 입력받습니다.

위에서 나타냈던 인접행렬처럼 mat배열에 인접행렬을 표현합니다.

그 후에 dfs와 bfs 함수를 호출하게 되는데요, 인자로 V를 넣은 이유는 노드 V부터 출발해서 탐색하기 때문이죠.

그럼 메인을 파악했으니 dfs 함수와 bfs함수를 살펴보겠습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
 
void dfs(int v) {
    
    cout << v << ' ' ;
    visit[v] = 1;            //방문한 노드를 visit 0에서 1로 변경
    for(int i=1; i<=N; i++) {
        if(visit[i] == 1 || mat[v][i] == 0)     
            continue;
        dfs(i);                //dfs에서 재귀를 사용
    }
}
 
cs

 

dfs함수입니다. 매개변수로 들어온 시작 노드 V를 먼저 출력하고, visit배열을 선언한곳에 1로 바꿈으로써, 출력한 노드를 지나갔음을 확인 할 수 있습니다.

그 다음, for문을 통해서 입력받은 노드 수만큼 탐색을 돌려주고, if 조건문을 통해서 그곳이 지나간 노드인지, 아직 방문하지 않은 노드인지를 확인합니다.

그와 동시에 OR 연산을 통해서 인접행렬이 1이면 서로 연결되있는 노드라서 dfs를 통해 다시 재귀로 들어가게되고, 그게 아니라면 continue를 통해 다음 반복문을 실행합니다.

 

이 과정을 통해 DFS를 마치게 되면, 메인에서 호출했던 dfs 함수에의해 DFS 결과가 화면에 출력이 되겠죠.

근데, 여기서 방문했던 visit 배열을 0에서 1로 바꾸었으니, 바로 다음 bfs 함수를 실행시켜야 되는데, 방문체크를 할 경우 모두 1로 바뀌어있어서 dfs와 마찬가지로 방문체크를 visit[i] == 1 이런식으로 하면 안됩니다. 그래서 어떤식으로 비교를 했는지 아래 bfs 코드를 통해 확인하겠습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void bfs(int v) {
    queue<int> q;            //bfs에서는 q를사용
    q.push(v);
    visit[v] = 0;            //방문한 노드를 visit 1에서 0으로 변경
    while(!q.empty()) {
        v = q.front();
        cout << q.front() << ' ';
        q.pop();
        for(int i=1; i<=N; i++) {
            if(visit[i] == 0 || mat[v][i] == 0)
                continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}
cs

 

 

bfs 함수도 시작노드 V로 받습니다 (V는 전역변수로 선언된 하나의 값만 들어오므로 바뀌지 않음)

큐를 사용하여 차수 순으로 순차적으로 탐색합니다.

원리는 코드를 보면 파악이 되실겁니다..

위에서 dfs와 다르게 visit[i] == 0으로 조건탐색을 하는 이유는 설명했듯이, 이미 visit배열이 1로 바뀌어있기 때문에 여기서는 방문한 노드의 visit를 0 으로 바꾸고, 조건을 확인하기 때문입니다.

 

 

이상으로, DFS BFS 포스팅을 마치겠습니다.

다시한번 !!! 임시저장을 생활화하자!!!!

'알고리즘' 카테고리의 다른 글

[백준알고] [2468]:안전 영역  (4) 2018.01.15
[백준알고] [2178]:미로 탐색  (2) 2018.01.14
[백준알고] [1697]:숨바꼭질  (3) 2018.01.14
[백준알고] [6603]:로또  (3) 2017.12.31

Today :
Yesterday :
Total :