[BOJ]1260 DFS와 BFS

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)의 구현 문제이다.

단순 구현 문제이지만 대회를 준비하는 시점에서 MAX_N의 값이 클 때를 대비해 adjacency matrix(인접 행렬)이 아닌 adjacency list(인접 리스트)로 구현하였다.

두 탐색법 모두 구현방법은 비슷하지만 DFS는 탐색을 시작한 노드에서 이어진 제일 깊은 노드까지 탐색하다 보니 재귀적으로 구현하는 점이 다르다고 볼 수 있겠다.

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

#include <cstdio>
#include <queue> // for BFS
#include <vector> //stack overflow를 방지하기 위해 
#include <algorithm> //for sort()
using namespace std;
 
#define MAX_N 1000
 
vector<int> adj_list[MAX_N+1]; // adjacency list
int N, M, start;
 
vector<int> bfs_vector, dfs_vector;
 
void dfs(int i, vector<bool> &visited) {
    visited[i] = true;
    dfs_vector.push_back(i);
    
    for(int k=0; k<adj_list[i].size(); k++) {
        int j = adj_list[i][k];
        if(!visited[j]) {
            dfs(j, visited);
        }
    }
}
 
void bfs() {
    queue<int> q; //방문할 노드 목록을 유지 
    vector<bool> visited_bfs(N+1, false);
    
    q.push(start);
    visited_bfs[start] = true;
    while(!q.empty()) {
        int i = q.front(); q.pop();
        bfs_vector.push_back(i);
        
        for(int k=0; k<adj_list[i].size(); k++) {
            int j = adj_list[i][k];
            if(!visited_bfs[j]) {
                q.push(j);
                visited_bfs[j] = true;
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d", &N, &M, &start);
    
    for(int m=0; m<M; m++) {
        int i, j;
        scanf("%d %d", &i, &j);
        adj_list[i].push_back(j);
        adj_list[j].push_back(i); //undirected graph이기 때문에 양방향을 이어준다. 
    }
    
    for(int i=1; i<=N; i++) //노드 번호 순으로 정렬 
        sort(adj_list[i].begin(), adj_list[i].end());
        
    vector<bool> visited_dfs(N+1, false);
    
    bfs();
    dfs(start, visited_dfs);
    
    for(int i=0; i<N; i++)
        printf("%d ", dfs_vector[i]);
    printf("\n");
    for(int i=0; i<N; i++)
        printf("%d ", bfs_vector[i]);
        
    return 0;
}

9561577

kim@@@@@

1260

맞았습니다!!

1388 KB

4 ms

C++14 / 수정

1513 B

6분 전