[백준] 1260 DFS와 BFS (그래프 탐색 / C언어 )

 

이번 학기( 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);
}