그래프 탐색

DFS 탐색 - 깊이 우선 탐색

스택을 이용하여 갈 수 있는 만큼 깊이 들어가며 탐색을 한다.

DFS 기본 코드

인접 행렬 이용

void dfs(int x){
    check[x] = true;
    for(int i=1;i<=n;i++){
        if(a[x][i] == 1 && check[i] == false){
            dfs(i);
        }
    }
}

인접 리스트를 이용한 구현

void dfs(int x){
    check[x] = true;
    for(int i=0;i<a[x].size();i++){
        int y = a[x][i];
        if(check[y] == false){
            dfs(y);
        }
    }
}

BFS 탐색 - 너비 우선 탐색

큐를 이용하여 지금 위치에서 갈 수 있는 정점을 모두 큐에 넣는다. 큐에 넣으면, 방문하였다고 체크해야한다.

BFS 기본 코드

인접행렬을 이용

queue<int> q;
    check[1] = true;
    q.push(1);
    while (!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=1;i<=n;i++){
            if(a[x][i]==1 && check[i] == false){
                check[i] = true;
                q.push(i);
            }
        }
    }

인접리스트 이용

queue<int> q;
    check[1] = true;
    q.push(1);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i=0;i<a[x].size();i++){
            int y = a[x][i];
            if(check[y] == false){
                check[y] = true;
                q.push(y);
            }
        }
    }   

오늘의 문제:

백준 1260, 백준 11724