이번 학기( 2024년 1학기 ) 자료구조를 배우며 그래프 활용에 대해 어려움을 많이 겪었다.
끝나고 몇 번의 복습을 거쳐서 이 문제에 적용하여 풀게 되었다.
그래프를 표현하기 위한 대표적인 자료구조 설정은 인접행렬과 인접리스트 방법이 있다.
그래프 표현 후에 DFS( 깊이 우선 탐색 )와 BFS ( 너비 우선 탐색 )을 활용하여 푸는 문제이다.
백준 기준으로 실버 2인 문제이다.
https://www.acmicpc.net/problem/1260
여기서 그래프 이론을 알기 전에 DFS와 BFS가 무엇인지부터 알아야 풀 수 있는 지식이 필요한 문제이다.
EX ) 인접리스트
( 그래프 탐색은 dfs bfs 둘 다 사용이 가능하다 ! )
DFS ( 스택 활용 / Depth First Search ) >> 임의의 정점을 설정하여 그 정점 시작으로 연결된 정점을 계속 따라 내려가면서 stack의 자료구조를 활용한다.
즉, 안 돌아가고 한 번에 최대치로 연결되어 있는 정점들이 어디까지 있는지 탐색을 하는 방식이다. stack에 백트래킹을 생각하면 된다.
깊이 우선 탐색은 경로를 설정할 때 특징성을 띄워야 할 때 사용을 한다.
- 그래프 탐색 dfs c언어 코드
void dfs(int V) {
visit[V] = 1;
printf("%d ", V);
for(int i=1; i<=N; i++)
{
if(graph[V][i] && !visit[i])
{
dfs(i);
}
}
}
BFS ( 큐 활용 / Bread First Search ) >> 임의의 정점을 설정하여 그 정점 시작으로 인접한 노드를 찾아가는 방식으로 만약
인접한 노드가 없으면 내려가서 다시 인접한 노드를 찾아가는 방식을 활용하여 queue를 활용한다.
너비 우선 탐색의 대표적인 예로는 미로 찾기가 있다. 즉 최단거리를 구해야 할 때 사용하는 방식이다.
- 그래프 탐색 bfs c언어 코드
void bfs(int V) {
int front = 0, rear = 1, pop;
visit[V] = 1;
printf("%d ", V);
queue[0] = V;
while(front < rear) {
pop = queue[front++];
for(int i=1; i<=N; i++)
if(graph[pop][i] && !visit[i]) {
visit[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
문제
그래프 탐색의 특징은 방문된 점을 기억해주는 매개체 필요하다.
그래야 겹치지 않게 방문된 점을 순서대로 출력할 수 있다.
#include<stdio.h>
int N, graph[1001][1001] = {0, }, visit[1001] = {0, }, queue[1001];
void dfs(int V) {
visit[V] = 1;
printf("%d ", V);
for(int i=1; i<=N; i++)
{
if(graph[V][i] && !visit[i])
{
dfs(i);
}
}
}
void bfs(int V) {
int front = 0, rear = 1, pop;
visit[V] = 1;
printf("%d ", V);
queue[0] = V;
while(front < rear) {
pop = queue[front++];
for(int i=1; i<=N; i++)
if(graph[pop][i] && !visit[i]) {
visit[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
int main() {
int M, V, x, y;
scanf("%d %d %d", &N, &M, &V);
for(int i=0; i<M; i++) {
scanf("%d %d", &x, &y);
graph[x][y] = 1;
graph[y][x] = 1;
}
visit[V] = 1;
dfs(V);
for(int i=1; i<=N; i++) visit[i] = 0;
visit[V] = 1;
printf("\n");
bfs(V);
}
'알고리즘' 카테고리의 다른 글
[백준] 17609번 회문 / C언어 (0) | 2024.09.20 |
---|---|
[백준 / 올림피아드 ] 28325번 호숫가의 개미굴 ( DP , greedy / c언어) (0) | 2024.07.10 |
[백준] 1271번 엄청난 부자 / python (with c) (0) | 2024.05.02 |
[백준]12789번 도키도키 간식드리미 (스택/ C언어 ) (0) | 2024.04.24 |