/* DFS, BFS 가 왜 큐문제에 들어있습니꽈 그래프를 DFS 로 탐색한 결과와 BFS 로 탐색한 결과를 출력하는 프로그램을 작성해보도록 하겠스 니다. 정점 번호가 작은 것을 먼저 방문하고, 더 이ㅏㅇ 방문할 수 있는 점이 없는 경우 종료합니다. 정점 번호 정점의 개수, 간선의 개수 ㅏㅁ색을 시작할 정점의 번호가 주어집니다. 입력으로 주어지는 간선은 양방향입니다. 1 2 3 4 1 1 1 1 2 1 1 3 1 1 4 1 1 1 이렇게 되어 있고 스타트는 1에서 한다? 1,2 에서 한다이것인가요. */ #include <stdio.h> #include <iostream> using namespace std; 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; cout << v << endl; for (i = 1; i <= N; i++) { if (Graph[v][i] == 1 && DFSvisit[i] == 0) { DFS(i, N); } } return; } void BFS(int v, int N) { int front = 0, rear = 0, Pop, i; cout << v; queue[0] = v; rear++; BFSvisit[v] = 1; while (front < rear) { Pop = queue[front]; front++; for (i = 1; i <= N; i++) { if (Graph[Pop][i] == 1 && BFSvisit[i] == 0) { cout << i << " "; queue[rear] = i; rear++; BFSvisit[i] = 1; } } } } int main() { int N, M, Start; int i, x, y; cin >> N >> M >> Start; for (i = 0; i < M; i++) { cin >> x >> y; Graph[x][y] = 1; Graph[y][x] = 1; } DFS(Start, N); cout << endl; BFS(Start, N); return 0; } |
오랜만에 DFS, BFS 에 대해서 들어왔습니다. 이에 대해서 가장 간단하게 설명한 것 같은데, 왜 이것을 이해 못하고 있을까요? 이것에 대해 명확하게 공부하고 나아가도록 하겠습니다. 깊이 우선 탐색, 너비 우선 탐색, return 하는 곳을 명확히 파악하기, 오케이요. 재귀함수를 사용합니다. |