1260번 DFS와 BFS 문제를 풀어보았다.

1260 DFS와 BFS

 

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

1260번: DFS와 BFS

 

이 문제는 놀랍게도, 제목 그대로다.

단순히 그래프의 정점의 개수와 간선들의 연결이 입력되는데, 이를 DFS방식으로 탐색한 순서대로 출력하고, BFS방식으로 탐색한 순서대로 출력하는 문제이다.

우선 DFS와 BFS에 대하여 간단히 설명을 해보면, 뜻 자체는 Depth-First Search, Breadth-First Search, 즉, 깊이 우선 탐색과 너비 우선 탐색이다.

DFS는 그래프의 연결된 상위간선에서 하위간선 식으로 이어서 탐색하는 느낌이다.

BFS는 그래프의 상위간선들을 우선 탐색하고 하위간선들을 탐색하는 느낌이다.

말로 표현하려니 무슨 소리인지 잘 모르겠으니, 단순히 알기 쉽게 나타내면 이러하다.

DFS	BFS

뭐, 대충은 이러한데, 이를 단순히 구현해서 저 간선에 연결된 정점에 들어가는 숫자를 간선이 연결된 순서대로 출력하면 되는 문제이다.

우선 DFS는 간선에 연결된 수와 연결된 수가 있는지를 체크하며, 있다면 그 수를 출력하고 그 수를 들렸다고 체크한다.

그리고 간선에 연결된 수가 없을 때까지 반복하면 간단히 구현할 수 있다.

BFS의 경우는 큐를 이용하였다.

큐에 간선의 처음 정점을 넣고, 그 수를 체크하고, 출력한다.

큐의 수가 전부 빠질때까지 front에 있는 수를 pop에 그 수에 간선으로 연결된 수들을 체크하고 큐에 넣어준다.

그리고 출력한다.

풀어놓고나서 드는 생각은 BFS와 DFS를 공부한지 꽤나 오래된 것 같은데, 이런 간단한 문제도 안풀어놨다는게 상당히 내 자신이 게을렀다는 생각이 들었다.

앞으로는 응용문제와 어려운 문제들도 많이 풀어봐야겠다.

 

#include <stdio.h>

int graph[1001][1001]={0};
int DFSvisit[1001]={0};
int BFSvisit[1001]={0};
int queue[1001];

void DFS(int v, int N) {
    int i;
    DFSvisit[v]=1;
    printf("%d ", v);
    for(i=1; i<=N; i++) if(!DFSvisit[i] && graph[v][i]) DFS(i,N);
}

void BFS(int v, int N) {
    int front=0,rear=0,pop,i;
    printf("%d ",v);
    queue[rear]=v;
    rear++;
    BFSvisit[v]=1;
    while(front<rear) {
        pop=queue[front];
        front++;
        for(i=0; i<=N; i++) {
            if(graph[pop][i] && !BFSvisit[i]) {
                printf("%d ",i);
                queue[rear]=i;
                rear++;
                BFSvisit[i]=1;
            }
        }
    }
}

int main()
{
    int n,m,start,i,x,y;
    scanf("%d %d %d",&n,&m,&start);
    for(i=0; i<m; i++) {
        scanf("%d %d", &x, &y);
        graph[x][y]=1;
        graph[y][x]=1;
    }
    DFS(start,n);
    puts("");
    BFS(start,n);
}