BOJ 1260 · DFS와 BFS

알고리즘 분류 : DFS, BFS  

DFS와 BFS의 기초를 다질 수 있는 문제이다.

DFS(Depth-First Search)란 깊이 우선 탐색의 줄임말로, 그래프에서 완전 탐색을 할 때 깊이를 우선순위로 탐색하는 방법을 말한다. 스택(Stack) 자료구조에 방문한 노드를 저장하면서 깊이 우선 탐색을 진행한다. 스택 자료구조(반복문으로 구현) 대신 재귀로 구현할 수 있다. 재귀 함수로 구현하면 스택 메모리를 사용하므로, 메모리 오버헤드가 발생할 수 있다. 재귀를 통한 DFS 구현이 스택 자료구조를 통한 DFS 구현보다 좀 더 코드가 깔끔하고 구현이 용이한 편이다.

BFS(Breadth-First Search)란 너비 우선 탐색의 줄임말로, 그래프에서 완전 탐색을 할 때 너비를 우선순위로 탐색하는 방법을 말한다. 큐(Queue) 자료구조에 방문한 노드를 저장하면서 너비 우선 탐색을 진행한다.

• 방법의 차이일 뿐, 모든 노드를 탐색한다면 둘 중 편한 것을 이용하면 된다. 단, 비가중치 그래프의 최단 경로 문제는 BFS를 이용해야 한다.
• DFS, BFS는 인접 행렬이나 인접 리스트로 구현할 수 있다. 일반적으로 인접 리스트 구현이 공간/시간복잡도 면에서 효율적이다.
• 두 방법 모두 하나의 노드는 한 번만 탐색하는 것을 원칙으로 하므로, 별도의 check 배열을 만들어서 방문 여부를 저장해야 한다.

---

C++ 소스코드 (인접 행렬)

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int n, m, v;
int a[1001][1001];
bool check[1001];

void dfs(int now) {
    check[now] = true;
    printf("%d ", now);
    for (int i=1; i<=n; i++) {
        if (a[now][i] &&!check[i]) {
            dfs(i);
        }
    }
}

void bfs(int v) {
    memset(check, false, sizeof(check));
    queue<int> q;
    q.push(v);
    check[v] = true;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        printf("%d ", now);
        for (int i=1; i<=n; i++) {
            if (a[now][i] && !check[i]) {
                check[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &v);
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x][y] = 1;
        a[y][x] = 1;
    }
    dfs(v);
    printf("\n");
    bfs(v);
    printf("\n");
    return 0;
}

✓ queue는 STL에 있는 queue 라이브러리를 사용했다.

✓ memset을 통해 check를 false로 초기화했다. 먼저 DFS에서 방문체크를 했기 때문에, BFS에서 다시 사용하려면 초기화가 필요하다.

✓ 인접리스트 방식은 STL의 vector를 이용하면 된다.

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, v;
vector<int> a[1001];
bool check[1001];

void dfs(int now) {
    check[now] = true;
    printf("%d ", now);
    for (int i=0; i<(int)a[now].size(); i++) {
        int next = a[now][i];
        if (!check[next]) {
            dfs(next);
        }
    }
}

void bfs(int v) {
    memset(check, false, sizeof(check));
    queue<int> q;
    q.push(v);
    check[v] = true;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        printf("%d ", now);
        for (int i=0; i<(int)a[now].size(); i++) {
            int next = a[now][i];
            if (!check[next]) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &v);
    for (int i=0; i<m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i=1; i<=n; i++) {
        sort(a[i].begin(), a[i].end());
    }
    dfs(v);
    printf("\n");
    bfs(v);
    printf("\n");
    return 0;
}

---

Python 3 소스코드 (인접 행렬)

import sys
from collections import deque
n, m, v = map(int, sys.stdin.readline().split())
a = [[0 for _ in range(n+1)] for _ in range(n+1)]
c = [False] * (n+1)

def dfs(now):
    c[now] = True
    print(now, end=' ')
    for i in range(1, n+1):
        if a[now][i] == 1 and c[i] is False:
            dfs(i)

def bfs(v):
    c = [False] * (n+1)
    q = deque()
    q.append(v)
    c[v] = True
    while q:
        now = q.popleft()
        print(now, end=' ')
        for i in range(1, n+1):
            if a[now][i] == 1 and c[i] is False:
                c[i] = True
                q.append(i)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    a[x][y] = 1
    a[y][x] = 1

dfs(v)
print()
bfs(v)
print()

✓ 입출력 속도 향상을 위해 input() 대신, sys.stdin.readline()을 사용했다.

✓ queue는 list를 써도 상관없지만, 연산이 많으면 collections의 deque이 더 효율적이다.

import sys
from collections import deque
n, m, v = map(int, sys.stdin.readline().split())
a = [[] for _ in range(n+1)]
check = [False]*(n+1)

def dfs(now):
    check[now] = True
    print(now, end=' ')
    for i in a[now]:
        if check[i] is False:
            dfs(i)

def bfs(v):
    check = [False]*(n+1)
    q = deque()
    q.append(v)
    check[v] = True
    while q:
        now = q.popleft()
        print(now, end=' ')
        for i in a[now]:
            if check[i] is False:
                check[i] = True
                q.append(i)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    a[x].append(y)
    a[y].append(x)

for i in range(1, n+1):
    a[i].sort()

dfs(v)
print()
bfs(v)
print()

---

참고

• 백준 온라인 저지 : BOJ 1260
• 위키피디아 : 그래프
• 위키피디아 : 깊이 우선 탐색
• 위키피디아 : 너비 우선 탐색