[BOJ 1260 C++] DFS와 BFS

1260번: DFS와 BFS

문제 분석

• 시간제한 : 2초 (약 2억 연산)
• 그래프의 간선이 주어졌을때, DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)을 구현하는 문제
• 주의사항 : 어떤 노드와 연결 된 노드가 여러 개 일때 작은 값 부터 방문할 것
• bool형 이차원 matrix를 만들어 i와j 번째 노드가 연결되어 있으면 matrix[i][j]는 true, 아니면 false

DFS (깊이 우선 탐색)

• DFS(v) : 정점 v를 방문했다고 처리해주고 matrix[v][i](i = 1~n)에 대해 값이 true면 DFS(i) 실행
  이를 재귀적으로 반복

BFS (너비 우선 탐색)

• 큐 생성 (FIFO)
• 큐에 들어간 모든 원소에 대해 아래를 반복
  • 큐의 front v를 꺼내 v에 대해 방문했다고 처리해주고 
  • v와 연결된 정점을 큐에 삽입

#include <iostream>
#include <queue>

using namespace std;

int n, m, first, v1, v2;
bool graph[1001][1001];
bool visited[1001];

void DFS(int x) {
    cout << x << " ";
    visited[x] = true;
    for (int i = 1; i <= n; i++) {
        if (graph[x][i] && !visited[i])
            DFS(i);
    }
}

void BFS() {
    queue<int> q;
    q.push(first);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (visited[x]) continue;
        visited[x] = true;
        cout << x << " ";
        for (int i = 1; i <= n; i++) {
            if (graph[x][i] && !visited[i])
                q.push(i);
        }
    }
}

int main() {
    cin >> n >> m >> first;

    while (m--) {
        cin >> v1 >> v2;
        graph[v2][v1] = true;
        graph[v1][v2] = true;
    }
    DFS(first);
    cout << endl;
    for (int i = 1; i <= n; i++)//BFS 실행전 방문처리 배열 초기화
        visited[i] = false;
    BFS();
}

배운 점

• 사실 DFS와 BFS를 처음 배울때 이론적으로만 이해했지 코드를 정확히 짜기 힘들어 했다.
  하지만 이 문제를 풀며 확실히 코드적으로도 이해하며 DFS,BFS 코드에 대한 자신감이 조금 생겼다.