[백준] 1260. DFS와 BFS

https://www.acmicpc.net/problem/1260

 

깊이 우선 탐색(DFS)과 넓이 우선 탐색(BFS)를 구현해보는 간단한 예제이다.

 

깊이 우선 탐색은 재귀 함수를 이용하여서 탐색하고, 넓이 우선 탐색은 자료 구조 중 하나인 큐를 이용해서 탐색한다.

 

C언어로 풀 때에는 구조체를 이용해 큐를 구현하였다.

 

---

C

#include <stdio.h>
#define MaxSize 1000000

int edge1[1001][10001];
int edge2[1001][10001];
int check1[1001];
int check2[1001];

// Queue
typedef struct{
    int data[100000];
    int len;
    int front;
    int rear;
} Queue;
void initQueue(Queue* q){
    q->len = 0;
    q->front = 0;
    q->rear = 0;
}
int popleft(Queue* q){
    if(q->len > 0){
        int res = q->data[q->front];
        q->front += 1;
        q->len -= 1;
        if(q->front == MaxSize) q->front = 0;
        return res;
    }
}
void append(Queue* q, int v){
    int idx = q->rear;
    q->data[idx] = v;
    q->rear += 1;
    q->len += 1;
    if(q->rear == MaxSize) q->rear = 0;
}

// edge 관련 함수들
int edgeLen(int num, int idx){
    int cnt = 0;
    for(int i = 0; i < 10001; i++){
        if(num == 1 && edge1[idx][i] == 0) break;
        else if(num == 2 && edge2[idx][i] == 0) break;

        if(num == 1 && edge1[idx][i] != -1) cnt++;
        else if(num == 2 && edge2[idx][i] != -1) cnt++;
    }
    return cnt;
}
int edgeMin(int num, int idx){
    int min = 100000;
    for(int i = 0; i < 10001; i++){
        if(edge1[idx][i] != -1){
            if(num == 1 && edge1[idx][i] == 0) break;
            if(num == 1 && edge1[idx][i] < min) min = edge1[idx][i];
        }

        if(edge2[idx][i] != -1){
            if(num == 2 && edge2[idx][i] == 0) break;
            if(num == 2 && edge2[idx][i] < min) min = edge2[idx][i];
        }
    }
    return min;
}
int edgeIndex(int num, int index, int v){ // edge[index] 중에서 v값 찾은 후 몇번째에 있는지 반환
    for(int i = 0; i < 10001; i++){
        if(num == 1 && edge1[index][i] == 0) break;
        if(num == 1 && edge1[index][i] == v) return i;

        if(num == 2 && edge2[index][i] == 0) break;
        if(num == 2 && edge2[index][i] == v) return i;
    }
    return -1;
}


void DFS(int v){
    check1[v] = 1;
    printf("%d ", v);

    int l = edgeLen(1, v);
    while(edgeLen(1, v) > 0){
        if(check1[edgeMin(1, v)] == 0) DFS(edgeMin(1, v));
        edge1[v][edgeIndex(1, v, edgeMin(1, v))] = -1;
    }
}

void BFS(int v){
    Queue q;
    initQueue(&q);
    check2[v] = 1;
    append(&q, v);

    while(q.len > 0){
        int a = popleft(&q);
        printf("%d ", a);
        while(edgeLen(2, a) > 0){
            int min = edgeMin(2, a);
            if(check2[min] == 0){append(&q, min); check2[min] = 1;}
            edge2[a][edgeIndex(2, a, min)] = -1;
        }
    }
}

int main() {
    int n, m, v; scanf("%d %d %d", &n, &m, &v);

    for(int i = 0; i < m; i++){ // 입력
        int a, b;
        scanf("%d %d", &a, &b);

        for(int j = 0; j < 10001; j++)
            if(edge1[a][j] == 0) {edge1[a][j] = b; edge2[a][j] = b; break;}
        for(int j = 0; j < 10001; j++)
            if(edge1[b][j] == 0) {edge1[b][j] = a; edge2[b][j] = a; break;}
    }
    DFS(v);
    printf("\n");
    BFS(v);
}

---

Python

from collections import deque
import copy
import sys
sys.setrecursionlimit(10 ** 6)

def BFS(v):
    q = deque()
    q.append(v)
    check[v] = True

    while len(q) > 0:
        a = q.popleft()
        print(a, end=" ")
        while len(edge[a]) > 0:
            if check[min(edge[a])] == False:
                q.append(min(edge[a]))
                check[min(edge[a])] = True
            del edge[a][edge[a].index(min(edge[a]))]
def DFS(v):
    check[v] = True
    print(v, end=" ")

    l = len(edge[v])
    while len(edge[v]) > 0:
        if check[min(edge[v])] == False:
            DFS(min(edge[v]))
        del edge[v][edge[v].index(min(edge[v]))]

n, m, v = map(int, input().split())

edge = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)
# print(edge)
t = copy.deepcopy(edge)

check = [False for _ in range(n+1)]
DFS(v)
print()
edge = copy.deepcopy(t)
check = [False for _ in range(n+1)]
# print(edge)
BFS(v)