[C언어] 백준 1260 DFS와 BFS

문제

그래프를 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 

예제 입력 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

1 2 4 3 1 2 3 4

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

1260번: DFS와 BFS

깊이 우선 탐색 알고리즘인 DFS(Depth First Search)와

너비 우선 탐색 알고리즘인 BFS(Breadth First Search) 알고리즘 문제입니다.

 

두 알고리즘의 심화 문제는 아니고 기본 형태를 구현할 수 있는지를 묻는 문제이기에

두 알고리즘을 알고만 있다면 어렵지 않게 풀 수 있을겁니다.

 

먼저 DFS쪽의 코드를 먼저 보겠습니다.

void    dfs(int next)
{
    printf("%d ", next);
	for (int j = 1; j <= n; j++)
	{
		if (t_node[next][j] && !dfs_vis[j])
		{
			dfs_vis[j]++;
			dfs(j);
		}
	}
}

void	dfs_1(int next)
{
	for (int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if (t_node[next][j] && !dfs_vis[j])
			{
				dfs_vis[j]++;
				printf("%d ", j);
				dfs_1(j);
			}
		}
	}
}

dfs를 통해 맨 처음 시작되는 노드를 next로 설정해 재귀를 돌립니다.

재귀 조건은 현재 노드 (next)가 다른 노드(j)와 연결되어 있으면서 아직 방문하지 않았다면 dfs_vis[j]

재귀호출 해줍니다.

이렇게 dfs를 먼저 돌리고 

"단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고"

문제에서 요구하는 것을 맞춰줘야 하기 때문에

dfs_1 함수를 따로 호출해서 나머지 정점 번호가 작은 것부터 출력해 주면 됩니다.

이런식으로 dfs를 먼저 끝낸 뒤 bfs의 출력 결과 또한 내야합니다.

 

보통 BFS는 큐 자료구조를 많이 이용하죠??

그런데 C언어에서는 큐 자료구조를 지원하지 않습니다.

그래서 직접 만들어서 써야하는데 이때 배열로 만들지 링크드 리스트로 만들지 선택지는 보통 두개입니다.

배열로도 동적할당을 하면 할 수 있겠지만 가독성이 떨어지고 헷갈려서 일반적으로 링크드 리스트를 이용해 큐를 만듭니다.

저 또한 링크드 리스트를 사용해서 큐를 직접 만들어서 BFS를 구현했습니다.

 

그럼 BFS 코드를 보시죠

typedef struct q
{
	int 		content;
	struct q	*next;
	struct q	*prev;
}	node;
node *head, *tail;

void	create_queue(void)
{
	head = (node *)malloc(sizeof(node));
	tail = (node *)malloc(sizeof(node));
	head->content = 0;
	head->next = tail;
	head->prev = NULL;
	tail->content = 0;
	tail->next = NULL;
	tail->prev = head;
}

node	*create_node(int content)
{
	node *temp;

	temp = (node *)malloc(sizeof(node));
	temp->content = content;
	temp->next = NULL;
	temp->prev = NULL;
	return (temp);
}

큐 생성용 함수인 create_queue와 노드를 만들어 줄 create_node 함수 입니다.

int	pop(void)
{
	int		n;
	node	*temp;
	node	*second;

	temp = head->next;
	second = temp->next;
	head->next = second;
	second->prev = head;
	n = temp->content;
	free(temp);
	return (n);
}

void	push(node *temp)
{
	node	*last;

	last = tail->prev;
	last->next = temp;
	temp->prev = last;
	temp->next = tail;
	tail->prev = temp;
}

void	queue_free(node *temp)
{
	if (temp->next != NULL)
		queue_free(temp->next);
	free(temp);
}

노드들을 서로 연결시켜줄 push 함수와 가장 먼저 들어온 노드를 꺼내줄 pop함수

그리고 동적할당을 해제 시켜줄 queue_free함수입니다.

 

이렇게 필수 함수만 직접 구현해 큐를 만드셨다면 이제 본격적으로 BFS를 만들 차례입니다.

void	bfs(void)
{
	int	value;

	while (head->next != tail)
	{
		value = pop();
		for(int i = 1; i <= n; i++)
		{
			if (t_node[value][i] && !bfs_vis[i])
			{
				bfs_vis[i]++;
				printf("%d ", i);
				push(create_node(i));
			}
		}
	}
}

while로 큐가 빌 때까지 반복해줍니다.

최상단 요소의 값을 pop해주고 내부에서 for문으로 이중 반복을 하는데요

이때 출력해 주면서 새로운 노드들을 연결시켜 주는 조건을 걸어 주어야 합니다.

현재 노드(value)가 다른 노드(i)랑 연결 되어([value][i]) 있으면서 아직 그 노드를 방문하지 않았다면 !bfs_vis[i]

출력하고 방문 표시와 해당 노드를 push 해주면 됩니다.

 

생각 보다 간단하죠?

큐를 직접 구현하는데 시간이 걸릴 뿐 의외로 코드량은 적습니다.

 

int main(void)
{
    scanf("%d %d %d", &n, &t, &v);
    for(int i = 0; i < t; i++)
    {
        scanf("%d %d", &l, &m);
        t_node[l][m]++;
        t_node[m][l]++;
    }
    dfs_vis[v]++;
    dfs(v);
    dfs_1(1);
    printf("\n");
    create_queue();
    push(create_node(v));
    printf("%d ", v);
    bfs_vis[v]++;
    bfs();
    queue_free(head);
    return (0);
}

마지막으로 main 함수인데요

for문으로 입력을 받을 때 [l][m], [m][l] 두번  다 카운트를 해주었는데 이는

노드들이 서로 연결되어 있는것 이기 때문에 단방향이 아니라 양방향 처럼 둘 다 카운트를 해준겁니다.

dfs함수를 호출하기 전 시작 노드를 먼저 카운트를 해줍니다.

왜냐하면 dfs 함수 내 최상단에 출력 부분이 있기 때문에 미리 방문 처리를 해줍니다.

그리고 dfs_1로 작은 노드부터 마무리 탐색을 해주고 dfs를 끝냅니다.

 

bfs를 시작하기 전에는 시작 노드를 먼저 push와 출력을 해줍니다.

그리고 똑같이 방문처리를 하고 bfs함수 호출후 큐 자료구조를 다 썻으니 동적할당을 해제(queue_free) 해주면서 프로그램이 끝납니다.

 

 

dfs와 bfs의 기본 사용법을 얼마나 잘 아느냐를 묻는 문제로서 복습하기 좋은 문제인것 같습니다.

 

 

반응형

전체 코드

#include <stdio.h>
#include <stdlib.h>

typedef struct q
{
	int 		content;
	struct q	*next;
	struct q	*prev;
}	node;
node *head, *tail;
int t_node[1001][1001] = {}, dfs_vis[1001] = {}, bfs_vis[1001] = {};
int t, v, n, l, m;

void	dfs_1(int next)
{
	for (int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			if (t_node[next][j] && !dfs_vis[j])
			{
				dfs_vis[j]++;
				printf("%d ", j);
				dfs_1(j);
			}
		}
	}
}

void    dfs(int next)
{
    printf("%d ", next);
	for (int j = 1; j <= n; j++)
	{
		if (t_node[next][j] && !dfs_vis[j])
		{
			dfs_vis[j]++;
			dfs(j);
		}
	}
}

void	create_queue(void)
{
	head = (node *)malloc(sizeof(node));
	tail = (node *)malloc(sizeof(node));
	head->content = 0;
	head->next = tail;
	head->prev = NULL;
	tail->content = 0;
	tail->next = NULL;
	tail->prev = head;
}

node	*create_node(int content)
{
	node *temp;

	temp = (node *)malloc(sizeof(node));
	temp->content = content;
	temp->next = NULL;
	temp->prev = NULL;
	return (temp);
}

int	pop(void)
{
	int		n;
	node	*temp;
	node	*second;

	temp = head->next;
	second = temp->next;
	head->next = second;
	second->prev = head;
	n = temp->content;
	free(temp);
	return (n);
}

void	push(node *temp)
{
	node	*last;

	last = tail->prev;
	last->next = temp;
	temp->prev = last;
	temp->next = tail;
	tail->prev = temp;
}

void	queue_free(node *temp)
{
	if (temp->next != NULL)
		queue_free(temp->next);
	free(temp);
}

void	bfs(void)
{
	int	value;

	while (head->next != tail)
	{
		value = pop();
		for(int i = 1; i <= n; i++)
		{
			if (t_node[value][i] && !bfs_vis[i])
			{
				bfs_vis[i]++;
				printf("%d ", i);
				push(create_node(i));
			}
		}
	}
}

int main(void)
{
    scanf("%d %d %d", &n, &t, &v);
    for(int i = 0; i < t; i++)
    {
        scanf("%d %d", &l, &m);
        t_node[l][m]++;
		t_node[m][l]++;
    }
	dfs_vis[v]++;
    dfs(v);
	dfs_1(1);
    printf("\n");
	create_queue();
	push(create_node(v));
	printf("%d ", v);
	bfs_vis[v]++;
    bfs();
    queue_free(head);
    return (0);
}