[백준] 1260 DFS와 BFS C++ (BFS/DFS)

📌백준 1260 DFS와 BFS
https://www.acmicpc.net/problem/1260

BFS와 DFS문제는 처음이다. 다른 블로그를 참고하며 풀었다.
BFS는 큐 [선입선출 FIFO]
DFS는 재귀 + 브루트포스(완전탐색) [후입선출 LIFO]
를 사용한 방식이었다.
DFS는 스택을 사용하는 후입선출 방식이다. 재귀를 통해 시스템 스택을 사용한다.

그래프 표현 방식에는 인접 행렬과 인접 리스트가 있다.
인접 행렬은 2차원 배열(행렬) 형태이고 인접 리스트는 vector와 같은 배열 형태이다.
공간복잡도는 인접행렬 O(V^2), 인접리스트 O(V+E) 이고
시간복잡도는 각 노드별로 연결된 모든 노드 탐색 시 인접행렬 O(V), 인접리스트 O(E)이다.

인접리스트는 인접행렬보다 공간복잡도도 작고, 탐색시간도 비교적 빠른편이라서 인접리스트가 많이 쓰인다고 한다.
여기서는 인접행렬을 사용하였다.

• 먼저 DFS, BFS를 수행하기 위해선 그래프(인접행렬)와 방문기록이 필요하다.
• 인접행렬, 방문기록, 노드 수, 간선 수를 전역으로 선언한다.
• 전역으로 선언해주면 자동으로 0으로 초기화된다.
• main()에서 노드, 간선 개수와 시작점을 입력받고
  인접행렬에서 입력받은 두 노드가 만나는 곳에 1을 넣어준다. (1 = 연결됨을 의미)
• DFS를 수행하고, 순서대로 출력해준다.
• memset을 이용하여 초기화해준다. memset 사용법
• BFS를 수행하고, 순서대로 출력해주고 끝

1. DFS
방문기록에 넣어주고, 연결된 다른 요소들이 있는데 방문기록이 없을 경우 그 요소에 대해 DFS를 수행하고 이를 반복한다.(재귀)
2. BFS
방문기록에 넣어주고 큐를 생성한다. 큐에 현재노드를 push하고,
큐의 맨 앞 노드를 복사한 다음에 큐에서 지워준다. 복사한 노드와 연결된 다른 노드들이 있을 것이다. 그럼 그 노드들을 큐에 넣어준다. 순서는 상관없다. 그리고 그 노드들도 방문기록에 남겨준다. 이것을 큐가 빌 때까지 반복한다.

뭔가 BFS보다 DFS가 더 쉽게 느껴졌던 것 같다. 큐를 많이 사용해보지 않아서 그런걸까 골고루 적용해보면서 익혀야겠다.

코드

#include <iostream>
#include <queue>    //BFS에서 활용
#include <string.h> //memset 쓰려면 필요
using namespace std;

/* 전역으로 정의 - 자동 0 초기화 */
int arr[1001][1001]; //인접행렬
int visited[1001];   //방문기록
int N, M, V;

/* DFS - 재귀(시스템 스택 사용) (후입선출 LIFO) */
void DFS(int V)
{
    visited[V] = 1;   //시작점 방문기록
    cout << V << " "; //방문한 노드 출력

    for (int i = 1; i <= N; i++)
    {
        if (arr[V][i] == 1 && visited[i] == 0)
        {
            DFS(i); //스택에 i 넣는 셈
        }
        if (i == N)
            return;
    }
}

/* BFS - 큐 사용 (선입선출 FIFO) */
void BFS(int V)
{
    queue<int> q; //큐 생성
    q.push(V);    //시작노드 큐에 넣음

    while (!q.empty())
    {
        int next = q.front(); //큐 맨 앞에 값을 방문
        visited[next] = 1;    //방문기록
        cout << next << " ";  //방문한 노드 출력
        q.pop();              //큐에서 뺌

        //방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited[i] == 0)
            {
                q.push(i);         //큐에 넣어줌
                visited[i] = 1; // i 점은 미리 방문기록 - 안하면 중복으로 방문할 수도 있다
            }
        }
    }
    
}

int main()
{
    int u, v;
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        arr[u][v] = 1;
        arr[v][u] = 1; //자리바꿔서도 해주는 이유 : 무방향이기 때문
    }                  //입력 즉시 인접행렬에 넣어줌, 다 돌면 인접행렬 완성

    DFS(V); // DFS 수행

    cout << "\n";                        //개행
    memset(visited, 0, sizeof(visited)); //방문기록 visited 초기화

    BFS(V); // BFS 수행
}

📌참고
https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity