728x90
https://www.acmicpc.net/problem/1260
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
댓글