문제
그래프를 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 9991 2 4 3 1 2 3 4https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
깊이 우선 탐색 알고리즘인 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);
}'백준 C언어' 카테고리의 다른 글
| [C언어] 백준 1439 뒤집기 (0) | 2023.01.03 |
|---|---|
| [C언어] 백준 2563 색종이 (0) | 2023.01.03 |
| [C언어] 백준 10854 큐 (0) | 2023.01.01 |
| [C언어] 백준 1003 피보나치 함수 (0) | 2023.01.01 |
| [C언어] 백준 1966 프린터 큐 (0) | 2022.12.31 |
