# 백준 : DFS와 BFS(1260)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1260_DFS&BFS_Adjacent_Matrix)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

int vertex_number;
int matrix[1001][1001];
int check_DFS[10001];
int check_BFS[10001];
int queue_BFS[1001];

void DFS(int vertex) {
    check_DFS[vertex] = 1;
    cout<<vertex<<" ";
    for(int i=1; i<=vertex_number; i++) {
        if(!check_DFS[i] && matrix[vertex][i]) {
            DFS(i);
        }
    }
}

void BFS(int vertex) {
    int front_queue = 0;
    int rear_queue = 0;
    queue_BFS[rear_queue++] = vertex;
    check_BFS[vertex] = 1;
    cout<<vertex<<" ";
    while(front_queue < rear_queue) {
        for(int i=1; i<=vertex_number; i++) {
            if(!check_BFS[i] && matrix[queue_BFS[front_queue]][i]) {
                check_BFS[i] = 1;
                cout<<i<<" ";
                queue_BFS[rear_queue++] = i;
            }
        }
        front_queue++;
    }
}

int main(void) {
    // variables
    int start;  // start vertex;
    int front, end; // movement of line through vertexes
    int line_number;    // number of lines
    
    cin>>vertex_number>>line_number>>start;
    for(int i=0; i<line_number; i++) {
        cin>>front>>end;
        matrix[front][end] = matrix[end][front] = 1;
    }
    DFS(start);
    cout<<endl;
    BFS(start);
    cout<<endl;
    return 0;
}

풀이

DFS와 BFS는 굉장히 중요한 알고리즘 개념들이다. 일명 '빠른 길 찾기'와 연관되는 경우가 많은데, 너무 오래 전에 공부했던 내용이라 코딩에 어려움을 느껴서 이번에 다시 공부해보았다.
참고 사이트로는 다음과 같다.

DFS: http://blog.eairship.kr/268?category=431859
BFS: http://blog.eairship.kr/269?category=431859

어려웠던 부분은 DFS에서 재귀함수를 사용하는 것과, BFS에서 별도의 큐를 사용해서 vertex로 입력되는 값들의 순서를 지정해주어야 한다는 것 이었다. 
각 알고리즘에 대한 자세한 개념은 참고 사이트에서 너무 자세하고 명확하게 설명해주고 있기 때문에 별도로 기술하지는 않겠다.