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

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

1260번: DFS와 BFS

난이도: solved.ac 실버 2

 

 

DFS와 BFS를 구현하는 문제다

 

graph라는 2차원 배열을 통해 각 정점끼리 연결된 것을 표현하고

 

각 정점을 방문하면 visited라는 배열의 해당 index 값을 1로 바꿔주었다

 

그리고 BFS 한정으로 큐(Queue)를 사용했는데

 

front와 rear라는 변수를 통해 enqueue, dequeue할 때의 위치를 나타내었다

 

#include<stdio.h>
#include<string.h>
#define MAX 1001
 
int graph[MAX][MAX];
int visited[MAX];
int queue[MAX];
 
void DFS(int N, int V);
void BFS(int N, int V);
 
int main() {
	int N, M, V;
	scanf("%d %d %d", &N, &M, &V);
 
	int x, y, i, j;
	for (i = 0; i < M; i++) {
		scanf("%d %d", &x, &y);
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
 
	DFS(N, V);
	printf("\n");
	memset(visited, 0, sizeof(int) * (N + 1));
	BFS(N, V);
	return 0;
}
 
void DFS(int N, int V) {
	visited[V] = 1;
	printf("%d ", V);
	for (int i = 1; i <= N; i++) {
		if (visited[i] == 0 && graph[V][i]) {
			DFS(N, i);
		}
	}
	return;
}
 
void BFS(int N, int V) {
	int front = -1, rear = -1, pop;
	printf("%d ", V);
	visited[V] = 1;
	queue[++rear] = V;
 
	while (front < rear) {
		pop = queue[++front];
		for (int i = 1; i <= N; i++) {
			if (visited[i] == 0 && graph[pop][i]) {
				printf("%d ", i);
				visited[i] = 1;
				queue[++rear] = i;
			}
		}
	}
	return;
}