[백준/BOJ/C언어] 1260번 :: DFS와 BFS

 문제 링크 :: https://www.acmicpc.net/problem/1260

 

---

 Solution

 전형적인 DFS, BFS 문제입니다. DFS와 BFS에 대한 설명은 아래의 관련 글 링크에서 보실 수 있습니다. DFS와 BFS 알고리즘에 더해 알아야 할 것이 하나 더 있습니다. 바로 그래프의 표현 방법인데요. 보통 가장 많이 사용되는 방법은 2차원 배열로 구성된 인접 행렬(Adjacency matrix)이나 링크드 리스트(linked list)로 구현한 인접 리스트(Adjacency list)입니다. 제가 쓴 DFS와 BFS에 대한 설명글에서도 나와 있지만, 이해를 돕기 위해 인접 행렬과 인접 리스트가 어떤 것인지 예를 들어 보자면 다음 사진과 같습니다. 

 

 인접 리스트는 존재하는 간선만 표현하지만 인접 행렬의 경우 가능한 모든 쌍에 대해 그것이 존재하는지, 존재하지 않는지 표현하게 되겠죠. 그래프가 커지면 커질수록 비효율적일 것입니다. 하지만 1260번 문제의 경우 많은 공간을 필요로 하지 않기에 저의 경우는 인접 행렬로 그래프를 표현하였습니다.

---

 Code

 

#include <stdio.h>
#define MAX_VERTICES 1001
int DFS_V[MAX_VERTICES] = { 0, }; //DFS를 실행하면서 방문한 정점을 표시하기 위한 배열
int BFS_V[MAX_VERTICES] = { 0, }; //BFS를 실행하면서 방문한 정점을 표시하기 위한 
int graph[MAX_VERTICES][MAX_VERTICES] = { 0, };
int queue[MAX_VERTICES];
void dfs(int v, int vertices);
void bfs(int v, int vertices);
 
int main() {
    int vertices, edges, vertex, i, j;
    scanf("%d %d %d", &vertices, &edges, &vertex);
 
    while (edges--) {
        scanf("%d %d", &i, &j);
        graph[i][j] = 1;
        graph[j][i] = 1;
    }
 
    dfs(vertex, vertices);
    printf("\n");
    bfs(vertex, vertices);
 
    return 0;
}
 
void dfs(int v, int vertices) {
    int w;
    DFS_V[v] = 1;
    printf("%d ", v);
    for (w = 1; w <= vertices; w++) {
        if (graph[v][w] == 1 && DFS_V[w] == 0) {
            dfs(w, vertices);
        }
    }
}
 
void bfs(int v, int vertices) {
    int w;
    int front, rear, pop;
    front = rear = 0;
    printf("%d ", v);
    BFS_V[v] = 1;
    queue[0] = v; rear++;
    while (front < rear) {
        pop = queue[front]; front++;
        for (w = 1; w <= vertices; w++) {
            if (graph[pop][w] == 1 && BFS_V[w] == 0) {
                printf("%d ", w);
                queue[rear] = w; rear++;
                BFS_V[w] = 1;
            }
        }
    }
}

---

 Related

2019/07/09 - [코학/알고리즘] - [알고리즘] DFS와 BFS에 대해 알아보기