DFS(Depth First Search)

 

• 인접 리스트는 메모리 사용이 효율적이며, 노드와 연결된 간선만 저장합니다.
• 인접 행렬은 구현이 간단하며 노드 간의 연결 여부를 빠르게 확인할 수 있지만, 메모리 사용량이 많아질 수 있습니다.
• 두 구현 모두 DFS를 수행하며, 출력 결과는 동일합니다.

 

 

1. 인접 리스트

#include <iostream>
#include <vector>
using namespace std;

void DFS(int node, vector<vector<int>>& adjList, vector<bool>& visited) 
{
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adjList[node]) 
    {
        if (!visited[neighbor]) 
        {
            DFS(neighbor, adjList, visited);
        }
    }
}

int main() 
{
    int n, m; // n: 정점의 수, m: 간선의 수
    cin >> n >> m;

    vector<vector<int>> adjList(n + 1); // 인접 리스트 (1-based index)
    for (int i = 0; i < m; i++) 
    {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 무방향 그래프이므로 양방향 연결
    }

    vector<bool> visited(n + 1, false); // 방문 여부 확인 배열

    cout << "DFS using adjacency list: ";
    DFS(1, adjList, visited); // 1번 노드부터 DFS 시작
    cout << endl;

    return 0;
}

 

2. 인접 행렬

#include <bits/stdc++.h> // C++ 표준 라이브러리 포함
using namespace std;

int dy[4] = {-1, 0, 1, 0}; // 상, 우, 하, 좌 방향 이동을 위한 배열 (y축 이동)
int dx[4] = {0, 1, 0, -1}; // 상, 우, 하, 좌 방향 이동을 위한 배열 (x축 이동)
int n, m;                  // n: 배열의 행 수, m: 배열의 열 수
int a[104][104];           // 2차원 배열 (문제에서 주어진 입력 값 저장)
bool visited[104][104];    // 방문 여부를 기록하는 배열

// DFS 함수: (y, x) 좌표에서 시작하여 연결된 모든 노드를 탐색
void DFS(int y, int x) {
    visited[y][x] = 1; // 현재 좌표 방문 처리

    for (int i = 0; i < 4; i++) { // 상, 우, 하, 좌 4방향으로 이동
        int ny = y + dy[i];       // 다음 y 좌표 계산
        int nx = x + dx[i];       // 다음 x 좌표 계산

        // 배열 범위를 벗어나면 무시
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;

        // 이동하려는 좌표가 조건(값이 1)을 만족하고 방문하지 않았다면 탐색
        if (a[ny][nx] == 1 && !visited[ny][nx]) {
            DFS(ny, nx); // 재귀 호출을 통해 연결된 모든 노드 탐색
        }
    }
    return;
}

int main() {
    cin.tie(NULL); // 입력 속도 향상
    cout.tie(NULL); // 출력 속도 향상

    cin >> n >> m; // 배열 크기 입력 (n: 행, m: 열)

    // 2차원 배열 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j]; // 값 저장
        }
    }

    int ret = 0; // 연결된 컴포넌트의 수를 저장하는 변수

    // 배열 전체를 순회하며 DFS로 연결된 컴포넌트를 탐색
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 현재 좌표가 조건(값이 1)을 만족하고 방문하지 않았다면
            if (a[i][j] == 1 && !visited[i][j]) {
                ret++;       // 새로운 컴포넌트를 발견했으므로 증가
                DFS(i, j);   // 해당 컴포넌트를 DFS로 탐색
            }
        }
    }

    cout << ret << '\n'; // 총 연결된 컴포넌트 개수 출력
    return 0;
}

주석 요약

1. 전역 변수:
   • dy와 dx: 상하좌우로 이동하기 위한 배열.
   • a[104][104]: 입력받은 2차원 배열.
   • visited[104][104]: 특정 좌표를 방문했는지 여부를 저장.
2. DFS 함수:
   • 현재 위치에서 연결된 모든 노드를 탐색.
   • 4방향(상, 우, 하, 좌)으로 이동하며 연결된 모든 노드를 재귀적으로 방문.
3. main 함수:
   • 배열 입력 처리.
   • 방문하지 않은 노드에서 DFS 호출하여 컴포넌트를 탐색.
   • 연결된 컴포넌트의 개수를 계산해 출력.

---

코드 실행 흐름

1. 배열의 모든 좌표를 순회하며 조건(값이 1이고 방문하지 않음)을 만족하는 시작점을 찾음.
2. 해당 시작점에서 DFS를 호출하여 연결된 모든 노드를 탐색하고 방문 처리.
3. 새로운 연결 컴포넌트를 발견할 때마다 ret을 증가.
4. 결과로 총 연결된 컴포넌트의 개수를 출력.