본문 바로가기
코딩/C언어

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

by 철없는민물장어 2022. 11. 25.
728x90

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net


DFS,BFS를 예전에 파이썬으로 처음 배웠는데, C언어로 다시 해보려니 기억도 가물가물하고 익숙치가 않다

#include <stdio.h>
#pragma warning(disable:4996)

short int graph[1001][1001] = { 0, };
short int visited[1001] = { 0, };
int queue[1001];
int N;
void dfs(int v) {
	visited[v] = 1;
	printf("%d ", v);
	for (int i = 1; i <= N; i++)
	{
		if (visited[i] == 0 && graph[v][i] == 1) {
			dfs(i);
		}
	}
	return;
}
void bfs(int v) {
	int front=0, rear=0,pop;
	queue[rear++] = v;
	printf("%d ", v);
	visited[v] = 1;
	while (rear > front) {
		pop = queue[front++];
		for (int i = 1; i <= N; i++) {
			if (graph[pop][i] == 1 && visited[i] == 0) {
				visited[i] = 1;
				printf("%d ", i);
				queue[rear++] = i;
			}
		}
	}

}
int main() {
	int  M, V;
	int v1, v2;
	scanf("%d %d %d", &N, &M, &V);
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &v1, &v2);
		graph[v1][v2] = graph[v2][v1] = 1;
	}

	dfs(V);
	for (int i = 1; i <= N;i++)
		visited[i] = 0;
	printf("\n");
	bfs(V);
}

graph[][]를 동적할당으로 vertex 개수에 알맞게 만들어볼까 했는데,

더보기

이차원배열을 malloc하는것이 복잡하기도 하고, 딱히 동적할당을 할 필요는 없을 것 같아서 지웠다.

 

더보기

(참고로 이차원배열을 이런식으로 동적할당 받았었다)

scanf_s("%d %d %d", &n, &m, &r);

	short int* visited = (short int*)calloc(sizeof(short int),( n + 1));
	int **graph = (int**)malloc(sizeof(int*) * n+1);
	
	for (int i = 0; i <= n; i++) {
		graph[i] = (int*)calloc(sizeof(int) , n+1);
	}

dfs는 너무 간단하다.

시작지점 v를 먼저 방문하고,

v에서 갈 수 있고 && 아직 방문하지 않은 곳을 찾아

해당 vertex를 재귀함수로 돌리면 끝이다.

 

bfs는 queue가 필요하다.

queue를 따로 구현해놓고 써야하나? 했는데

그냥 bfs함수 내에다가 간단하게 큐의 방식대로 동작하게 코드를 짰다.

우선 시작지점v를 방문한다.

v에서 갈 수 있고 && 아직 방문하지 않은 곳을 찾아

해당 vertex를 방문처리하고 큐에 삽입한다.

v에서 갈 수 있는 곳을 모두 방문했다면, 큐에서 새로운 vertex를 하나 뽑고, 똑같이 반복한다.

큐가 완전히 비었을 때 종료한다.

 

728x90

댓글