[2025 1학기 알고리즘 스터디] 김민주 #4주차

알고리즘 스터디 4주차 : Graph

 

1. DFS와 BFS

https://www.acmicpc.net/problem/1260

 

---

💡문제 분석 및 알고리즘 설계

기본 DFS, BFS 구현 문제입니다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n,m,v;
vector <vector<int>> A;
vector <bool> visited;

void BFS(int now);
void DFS(int now);

int main(){
    //freopen("/home/user/cpp_baekjoon/input.txt", "r", stdin);
    cin >>n>>m>>v;
    A.resize(n+1);
    visited.resize(n+1, false);

    for (int i=0; i<m; i++){
        int n1,n2;
        cin >> n1 >> n2;
        // 양방향
        A[n1].push_back(n2);
        A[n2].push_back(n1);
    }

    for (int i=0; i<=n; i++){
        sort(A[i].begin(), A[i].end());
    }

    DFS(v);
    visited.assign(n + 1, false); // 방문 배열 초기화
    cout << "\n";
    BFS(v);
}

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

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

        for (int next: A[node]){
            if (!visited[next]){
                visited[next] = true;
                q.push(next);
            }
        }
    }
}


void DFS(int now){
    visited[now] = true;
    cout << now << " ";

    for (int node: A[now]){
        if (!visited[node]){
            DFS(node);
        }
    }
}

---

 

2. 연결 요소의 개수

https://www.acmicpc.net/problem/11724

 

---

💡문제 분석 및 알고리즘 설계

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

vector<int> vect[1001]; 
int visited[1001];
int N, M;

void DFS(int check){
    visited[check] = 1;
    for (int i = 0; i < vect[check].size(); i++){
        int idx = vect[check][i];
        if (visited[idx] == 0){
            DFS(idx);
        }
    }
}

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

    for (int i = 1; i <= N; i++){
        if (visited[i] == 0)
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

 

---

3. 미로 탐색

https://www.acmicpc.net/problem/2178

---

💡문제 분석 및 알고리즘 설계

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

int map[101][101];
int visited[101][101];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int n, m;

void bfs(int x, int y) {
	queue<pair<int, int>>q;
	q.push(make_pair(x, y));
	visited[x][y] = 1;

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

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

			if (0 <= nx &&nx < n && 0 <= ny && ny < m) {
				if (visited[nx][ny] == 0 && map[nx][ny] == 1) {					
					q.push(make_pair(nx, ny));

					visited[nx][ny] = visited[x][y] + 1;
				}
				else if (visited[nx][ny] == 0)
					visited[nx][ny] = -1;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];
	bfs(0, 0);
	cout << visited[n -1][m -1];
	cout << endl;
    return 0;
}