[백준] 1260번 : DFS와 BFS [C/C++]

#문제

1260번: DFS와 BFS

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

1260번: DFS와 BFS

 

---

#접근방법

그래프 탐색 기법 중 깊이우선탐색(dfs)과 너비우선탐색(bfs)를 사용하여 접근하였다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
using namespace std;

vector<int> v[1005];
int n,m,k;
int a,b;
int visit[1005];

void dfs(int x){
    printf("%d ",x);

    for(int i=0;i<v[x].size();i++){
        int node = v[x][i];

        if(visit[node]==0){
            visit[node] = 1;
            dfs(node);
        }
    }

    return;
}

void bfs(int first){
    queue<int> q;

    q.push(first);

    while(!q.empty()){
        int x = q.front();
        q.pop();

        printf("%d ",x);

        for(int i=0;i<v[x].size();i++){
            int node = v[x][i];

            if(visit[node]==0){
                visit[node] = 1;
                q.push(node);
            }
        }
    }

    return;
}

int main(){
    scanf("%d %d %d",&n,&m,&k);

    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);

        v[a].push_back(b);
        v[b].push_back(a);
    }

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

    visit[k] = 1;
    dfs(k);
    printf("\n");

    memset(visit,0,(n+1)*sizeof(int));

    visit[k] = 1;
    bfs(k);

    return 0;
}

 

그래프 탐색기법 중 깊이우선탐색(dfs)은 한 정점에서 연결된 노드들 중에서 한 방향으로 쭉 탐색을 하다가 막히면 돌아와서 다른 정점의 한 방향으로 쭉 탐색을 하면서 연결된 모든 노드를 탐색한다.

 

너비우선탐색(bfs)는 한 정정에서 연결된 노드들을 다 탐색을 하고 다음 방향을 가서 다시 연결된 노드를 다 탐색을 한다. 가까운 노드부터 탐색하고 멀리떨어져 있는 노드를 나중에 탐색을 한다.

 

dfs는 stack이라는 자료구조를 사용하여 구현한다. stack이란 먼저 들어온 것이 나중에 나가는 구조이다. 예를 들어 막대기에 도넛을 끼운다고 생각을 해보자. 여러개의 도넛을 끼우고 차례대로 뺀다면, 먼저 들어간 도넛이 나중에 나가게 된다.

 

하지만 위 코드의 dfs는 재귀함수로 구현을 하였는데 재귀함수도 stack처럼 호출한 함수들이 쌓여가면서 먼저 호출한 함수가 나중에 호출이 되는 구조이다. 따라서 재귀함수로도 dfs를 구현 할 수 있다.

 

bfs는 queue라는 자료구조를 사용하여 구현한다.  queue는 먼저 들어간 것이 먼저 나가는 구조이다. 예를 들어 놀이동산에 입장을 하려고 줄을 선다면 먼저 선 사람이 먼저 가게된다.

 

먼저 n,m,k를 입력받고 m개의 간선을 입력받는다. vector라는 자료구조로 입력을 받아주었다.

 

문제에서 방문할 수 있는 정점이 여러 개인 경우에는 작은 정점부터 탐색한다고 했으므로 sort함수로 오름차순으로 정렬해주었다.

 

방문을 확인하는 visit 배열에 시작점을 visit[k] = 1로 저장해주고 dfs(k)를 호출한다.

 

dfs함수가 호출 될 때 마다 printf를 하면서 x 정점에 인접한 정점들을 탐색해주면서 visit 배열에 방문여부를 확인하면 된다.

 

bfs함수를 호출하면 queue자료구조에 시작점을 넣어준다.

 

while(!q.empty())로 q가 빌 때까지 반복문을 돌아주면서 인접한 정점들을 다 q에 넣으면서 탐색을 하며 출력을 하면 된다.

 

---

#성능

---

#정리

그래프 탐색 기법 중 깊이우선탐색(dfs) 또는 너비우선탐색(bfs)를 아는 것,

 

이를 구현할 수 있으면 풀 수 있는 문제였다.