[백준(BOJ)] 1260번 DFS와 BFS C++

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

1260번: DFS와 BFS

 

어떤 문제인가?

그래프 탐색 방법인 dfs와 bfs를 통해 그래프를 탐색하는 순서를 출력하면 되는 간단한 문제이다.

 

 

접근 방법

 

bool visited[1001];
vector<int>graph[10001];

먼저 그래프를 저장할 벡터와 정점의 방문 여부를 저장할 배열이 필요하다.

 

 

int n,m,v;
cin >> n >> m >> v;

문제에서 주어진 변수들을 선언하고 입력받는다.

 

for(int i=0;i<m;i++){
    int a,b;
    cin >> a>>b;
    graph[a].push_back(b);
    graph[b].push_back(a);
}

간선이 m개이기 때문에 m번만큼 한 간선이 연결하는 두 정점을 입력받는다.

이때 양방향 그래프이기 때문에, a정점에도 b정점을 연결시켜주고, b정점에도 a정점을 연결시켜준다.

 

for(int i=1;i<=n;i++){
    sort(graph[i].begin(),graph[i].end());
}

문제의 조건에서 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다고 했으니

sort를 사용해 각 정점에 연결된 정점들을 오름차순으로 정렬해준다.

 

 

dfs(v);

이제 그래프를 입력받았으니 탐색을 시작한다. 먼저 dfs부터 시작한다.

 

void dfs(int x){
    cout << x << " ";
    visited[x] = true;
    for(int i:graph[x]){
        if(!visited[i]){
            dfs(i);
        }
    }
}

dfs 함수이다. 재귀의 방식을 통해 구현했다.

방문한 x정점을 출력하고 그 정점을 방문 처리해준다.

그리고 x정점에 연결되어있는 정점들이 만약 방문되지 않았다면 재귀를 통해 방문해주면 된다.

 

for (int i = 0; i <= n; i++) {
    visited[i] = false;
}

dfs가 끝났으니 bfs를 해줄 차례이다. 그전에, visited 배열을 모두 false로 해주어 미방문 처리를 해준다.

 

bfs(v);

void bfs(int x){
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        if (visited[top]) {
            continue;
        }
        visited[top] = true;
        cout << top << " ";
        for (int i: graph[top]) {
            if (!visited[i]) {
                q.push(i);
            }
        }
    }
}

bfs는 큐를 사용해 구현하였다.

탐색을 시작할 x정점을 큐에 추가해준다.

그리고 이제 큐가 빌 때까지 반목문을 통해 그래프를 탐색한다.

 

방문할 정점을 top이라는 변수에 저장해주고 큐를 팝 해준다.

그리고 만약 top정점이 이미 방문되었다면 comtinue를 통해 다음 반복을 진행한다.

반대로 방문되지 않았다면 방문처리를 해주고, top정점을 출력해준다.

 

이제 dfs와 비슷하게 top정점에 연결된 정점들이 만약 방문되지 않았다면 큐에 그 정점을 추가해준다.

그리고 반목문을 돌며 bfs가 계속 진행될 것이다.

 

 

무엇이 어려웠는가?

문제 자체가 큰 것을 요구하지 않고 기초적인 탐색만하는 것이었다.

학교에서 자료구조를 배우며 공부를 했던 부분이라 어려운 부분은 없었다.

 

 

시간 복잡도

dfs와 bfs 모두 인접리스트 방식으로 구현했으니 O(v+e)의 시간 복잡도를 갖는다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/DFS%EC%99%80%20BFS/1260.cpp