백준 1260번 BFS DFS 를 같이 사용하는 문제입니다.
앞서 포스팅했던, BFS는 Queue를 사용하고, DFS는 Stack을 사용하는것을 중점적으로 해서 문제를 풀었습니다.
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 [1]
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 [1]
1 2 4 3
1 2 3 4
예제 입력 [2]
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 [2]
3 1 2 5 4
3 1 4 2 5
예제 입력 [3]
1000 1 1000
999 1000
예제 출력 [3]
1000 999
1000 999
문제는 이렇게 구성되어있습니다.
먼저 제 풀이를 보여드리겠습니다.
#include <stdio.h>
#include <stdlib.h>
bool visit[1001] = { false, };
bool visit2[1001] = { false, };
int N, M, V;
typedef struct stack {
int data;
struct stack* next;
struct stack* prev;
}stack;
typedef struct tree {
struct stack* root;
int count;
}tree;
tree* init() {
tree* Tree = (tree*)malloc(sizeof(tree));
if (Tree == NULL) {
printf("err\n");
}
else {
Tree->root = NULL;
Tree->count = 0;
return Tree;
}
}
void push(tree* Tree, int data) {
stack* newStack = (stack*)malloc(sizeof(stack));
stack* preStack = Tree->root;
newStack->data = data;
if (Tree->count == 0) {
newStack->next = newStack;
newStack->prev = newStack;
Tree->root = newStack;
}
else {
for (int i = 0; i < Tree->count - 1; i++) {
preStack = preStack->next;
}
newStack->next = preStack->next;
preStack->next = newStack;
newStack->prev = preStack;
newStack->next->prev = newStack;
}
Tree->count++;
}
void Stackpop(tree* Tree) {
stack* deleteStack = Tree->root;
for (int i = 0; i < Tree->count - 1; i++) {
deleteStack = deleteStack->next;
}
deleteStack->prev->next = Tree->root;
Tree->root->prev = deleteStack->prev;
free(deleteStack);
Tree->count--;
}
void Queuepop(tree* Tree) {
stack* deleteQueue = Tree->root;
Tree->root = Tree->root->next;
deleteQueue->prev->next = deleteQueue->next;
deleteQueue->next->prev = deleteQueue->prev;
free(deleteQueue);
Tree->count--;
}
void stackprint(tree* Tree) {
stack* curStack;
int i;
for (i = 0, curStack = Tree->root; i < Tree->count; i++, curStack = curStack->next) {
printf("%d ", curStack->data);
}
//return curStack->data;
}
int catStack(tree* Tree) {
stack* curStack = Tree->root;
return curStack->prev->data;
}
int catQueue(tree* Tree) {
stack* curStack = Tree->root;
return curStack->data;
}
void DFS(int **arr,int V,tree *Tree) {
if (Tree->count == 0) {
push(Tree, V);
}
visit[V] = true;
for (int i = 1; i < N + 1; i++) {
if (arr[V][i] == 1 && !visit[i]) {
push(Tree, i);
DFS(arr,i,Tree);
}
}
}
void BFS(int **arr, int V, int N, tree* Tree) {
visit2[V] = 1;
push(Tree, V);
while (Tree->count != 0) {
V = catQueue(Tree);
printf("%d ", V);
for (int i = 1; i <= N; i++) {
if (arr[V][i] == 1 && !visit2[i]) {
visit2[i] = true;
push(Tree, i);
}
}
Queuepop(Tree);
}
}
int main() {
tree* Tree = init();
scanf("%d %d %d", &N, &M, &V);
int NUM = 1001;
int** arr = (int **)malloc(sizeof(int *) *NUM);
for (int i = 0; i < NUM; i++) {
arr[i] = (int*)malloc(sizeof(int) * NUM);
}
int num1, num2;
for (int i = 0; i < M; i++) {
scanf("%d %d", &num1, &num2);
arr[num1][num2] = arr[num2][num1] = 1;
}
DFS(arr,V,Tree);
stackprint(Tree);
printf("\n");
int K = Tree->count;
for (int i = 0; i < K; i++) {
Stackpop(Tree);
}
BFS(arr, V, N, Tree);
K = Tree->count;
for (int i = 0; i < K; i++) {
Stackpop(Tree);
}
for (int i = 0; i <NUM; i++) {
free(arr[i]);
}
free(arr);
free(Tree);
return 0;
}사용한 헤더는 stdio 와 stdlib 입니다.
stdio는 입출력을 이용하기 위해 사용하였고, stdlib는 동적할당을 이용하기 위해 사용했습니다.
stack 과 queue 구현은 이중원형연결리스트로 구현하였습니다.
이유는, stack 과 queue를 단일 연결리스트로 구현 할 수 있지만 그렇게 된다면 struct의 생성 수 가 많아지고, 코드가 복잡해지기 때문에 간단하게 이중원형연결리스트로 구현하여 , stack과 queue 기능 모두 사용 할 수 있게 만들었습니다.
맨 처음지점을 root 노드로 잡아서,
root->prev 로 이동해서 data를 계속 prev 하여 root 까지 도달하면, Queue. (LIFO)
root에서 data를 계속 next 하여 다시 root까지 도달하면 Stack 가 됩니다.(FIFO)
push는 들어오는 순서대로 push하게 하였으며, delete기능도 구현하여 반환 할 수 있게 만들었습니다.
이제 문제 풀이과정을 정리 해 보겠습니다.
저는 처음에 2차원 배열에 대하여 동적할당 하였습니다. 까닭은 나중에 메모리를 반환하기 위함입니다.
그리고 전역변수로 visit 배열 2개를 bool 타입으로 만들었습니다. 까닭은 data 영역의 메모리에 할당하기 위함입니다. 왜냐하면, main에서 변수를 여러가지 선언하여 stack영역에 메모리를 잡고있고, 이중원형연결리스트 와 2차원 배열이 힙영역의 메모리를 잡기때문에 메모리를 한쪽으로 부하시켜 메모리 누수를 방지하기 위해서 부족한 지식이지만 나름 열심히 짜 봤습니다.
dfs 와 bfs 함수로 들어갈때 visit를 이용하여 체크를 하였습니다. 원래는 visit 함수 하나를 만들어서 초기화 하면 더 효율적이겠지만, 초기화하는데에 연산 (문제조건 정점의개수 1000개) 이어서 (사실상 큰 문제는 없지만) 그냥 2개로 만들었습니다. 큰 이유는 없었습니다.
결과는 다 잘 나오구, 테스트케이스 또한 전부 잘 되는것을 확인하였습니다.
