[백준알고리즘]1260 DFS와 BFS

DFS와 BFS

 

 

 

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
5 초	128 MB	24720	7751	4631	29.510%

 

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

입력

첫째 줄에 정점의 개수 N(1≤N≤1,000), 간선의 개수 M(1≤M≤10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 한 간선이 여러 번 주어질 수도 있는데, 간선이 하나만 있는 것으로 생각하면 된다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

<코드>

#define MAX 1001
#include <stdio.h>

int Graph[MAX][MAX] = { 0 };
int BFSvisit[MAX] = { 0 };
int DFSvisit[MAX] = { 0 };
int queue[MAX];

//DFS 구현
int DFS(int v, int N)
{
 int i;
 DFSvisit[v] = 1;
 printf("%d ", v);

 for (i = 1; i <= N; i++)
 {
  if (Graph[v][i] == 1 && DFSvisit[i] == 0)
  {
   DFS(i, N);
  }
 }
 return 0;
}

//BFS구현!!

int BFS(int v, int N)
{

 int front = 0, rear = 0;
 int i, pop;

 BFSvisit[v] = 1;
 printf("%d ", v);
 queue[0] = v;
 rear++;

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

 }
 return 0;
}

int main()
{
 int N, M, v;
 int x, y;

 scanf("%d%d%d", &N, &M, &v);

 for (int i = 1; i <= M; i++)
 {
  scanf("%d%d", &x, &y);
  Graph[x][y] = 1;
  Graph[y][x] = 1;

 }

 DFS(v, N);
 printf("\n");
 BFS(v, N);

 return 0;
}