[백준 1260] DFS와 BFS [C]

백준 - 1260

---

풀이

DFS는 방문 기록이 없는 정점만 탐색하면 된다.

BFS는 방문한 정점을 visited뿐만 아니라 Queue에 순서대로 기록하고, front로 탐색의 기준점을, rear로 탐색의 중단점을 설정해주면 된다.

---

소스코드

#include <stdio.h>
#include <memory.h>
int N, arr[1001][1001], visited[1001], queue[1001];
void dfs(int v){
    visited[v] = 1;
    printf("%d ", v);
    for (int i = 1; i <= N; i++)
        if (arr[v][i] && !visited[i])
            dfs(i);
}
void bfs(int v){
    visited[v] = 1;
    printf("%d ",(queue[0] = v));
    int front = 0, rear = 1;
    while (front < rear){
        int pop = queue[front++];
        for (int i = 1; i <= N; i++)
            if (arr[pop][i] && !visited[i]){
                printf("%d ", i);
                queue[rear++] = i;
                visited[i] = 1;
            }
    }
}
int main(){
    int M, V, x, y;
    scanf("%d %d %d", &N, &M, &V);
    while (M--){
        scanf("%d %d", &x, &y);
        arr[x][y] = arr[y][x] = 1;
    }
    dfs(V);
    memset(visited, 0, sizeof(visited));
    putchar(10);
    bfs(V);
}

---

출처

1260번: DFS와 BFS