[2025 1학기 알고리즘 스터디] 신지은 #4주차

안녕하세요? 4주차 알고리즘 스터디 시작하겠습니다.

이번주에는 Graph 알고리즘에 대한 내용을 배우고 문제를 풀도록 하겠습니다.

 

Graph Algorithms

그래프는 정점(Node라고 불림)과 이걸 연결하는 간선으로 구성된 자료구조를 말합니다.

방향성이 있는 방향 그래프, 방향성이 없는 무방향 그래프로 분류할 수 있고

이러한 그래프 자료구조는 컴퓨너 네트워크, 교통 시스템, 소셜 미디어와 같은 다양한 현실 세계의 문제를 모델링하는데 사용됩니다.

 

우선 그래프 탐색 알고리즘에 대해 알아보겠습니다.

그래프에서 특정 정점을 찾는 알고리즘을 말하는데 그래프의 각 정점을 순회하면서 방문해야 하므로 그래프 순회 알고리즘으로 부르기도 합니다. 이 알고리즘 종류에는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)이 있습니다.

 

[DFS 작동 방식]

출발 정점에서 최대한 깊이 갈 수 있는 정점까지 가보고 더 이상 진행 못하는 경우에 다시 돌아와서 방문하지 않은 다른 정점부터 탐색을 시작하는 방식입니다.

 

[BFS 작동 방식]

그래프 탐색 시 가까운 인접 정점을 방문한 후에 그다음 가까운 인접 정점을 방문하는 방식입니다.

 

1. DFS와 BFS(https://www.acmicpc.net/problem/1260)

일단 BFS를 구현하기 위해서 queue가 필요합니다. 그 이유는 가까운 노드부터 차례대로 방문하는 BFS의 특성 때문인데 queue는 선입선출(FIFO)구조여서 먼저 방문한 노드의 이웃부터 먼저 처리할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX = 1001;
vector<int> graph[MAX];
bool visited[MAX];

void dfs(int v) {
    visited[v] = true;
    cout << v << " ";
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
        if (!visited[next]) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        cout << curr << " ";

        for (int i = 0; i < graph[curr].size(); i++) {
            int next = graph[curr][i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

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

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(V);
    cout << "\n";

    fill(visited, visited + MAX, false);
    bfs(V);
    cout << "\n";

    return 0;
}

 

2. 연결 요소의 개수(https://www.acmicpc.net/problem/11724)

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1001;
vector<int> graph[MAX];
bool visited[MAX];

void dfs(int v) {
    visited[v] = true;
    for (int next : graph[v]) {
        if (!visited[next]) {
            dfs(next);
        }
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int count = 0;
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            dfs(i);
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

 

3. 미로 탐색(https://www.acmicpc.net/problem/2178) - BFS

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int maze[100][100];
int dist[100][100];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 1;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (maze[nx][ny] == 1 && dist[nx][ny] == 0) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }

    return dist[N-1][M-1];
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < M; j++) {
            maze[i][j] = row[j] - '0';
        }
    }

    cout << bfs() << endl;

    return 0;
}

 

4주차 알고리즘 스터디 끝 !-!