그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기

 

그래프 - (백준 1260, 2606, 2667) DFS와 BFS, 바이러스, 단지번호붙이기

 

 

문제 출저 - 백준 https://www.acmicpc.net/problem/1260

 

 

 

my code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
 
vector<vector<int>> adj;
vector<bool> visited;
 
void dfs(int here) {
    cout << here << " ";
    visited[here] = true;
    size_t size = adj[here].size();
    for (size_t i = 0; i < size; ++i) {
        int there = adj[here][i];
        if (!visited[there]) {
            dfs(there);
        }
    }
}
 
void bfs(int start) {
    vector<bool> discovered(adj.size() , false);
    queue<int> q;
    discovered[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        cout << here << " ";
 
        size_t size = adj[here].size();
        for (size_t i = 0; i < size; ++i) {
            int there = adj[here][i];
            if (!discovered[there]) {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int N, M, V;
    cin >> N >> M >> V;
 
    adj = vector<vector<int>>(N + 1);
    visited = vector<bool>(N+1, false);
 
    while (M--) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    for (int i = 1; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }
 
    dfs(V);
    cout << "\n";
    bfs(V);
}

 

 

 

 

 

 

 

 

문제 출저 - 백준 https://www.acmicpc.net/problem/2606

 

 

 

 

 

my code (DFS)

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<vector<int>> adj;
vector<bool> visited;
 
int dfs(int here) {
    int count = 1;
    visited[here] = true;
 
    size_t size = adj[here].size();
    for (size_t i = 0; i < size; ++i) {
        int there = adj[here][i];
        if (!visited[there]) {
            count += dfs(there);
        }
    }
    return count;
}
 
int main() {
    cin.sync_with_stdio(false);
 
    int com; // <= 100
    int n;
 
    cin >> com;
    cin >> n;
 
    adj = vector<vector<int>>(com + 1);
    visited = vector<bool>(com + 1, false);
 
    while (n--) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    cout << dfs(1) - 1;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 출저 - 백준 https://www.acmicpc.net/problem/2667

 

 

 

 

 

my code (BFS)

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
const int type[4][2] = {
    {0,-1}, {0,1}, {-1,0}, {1,0}
};
 
int board[26][26] = { 0 };
int block, cnt; // 단지개수, 집개수
vector<int> cntVec; // 집개수 배열
 
void bfs() {
    int size = 25;
    vector<vector<bool>> discovered(size+1, vector<bool>(size+1, false));
    queue<pair<int, int>> q;
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            if (board[i][j] == 1 && !discovered[i][j]) {
                discovered[i][j] = true;
                q.push(make_pair(i, j));
                cnt = 0;
                while (!q.empty()) {
                    pair<int, int> nyx = q.front();
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        const int ny = nyx.first + type[k][0];
                        const int nx = nyx.second + type[k][1];
                        // 바깥 방지
                        if (ny < 0 || ny >= size || nx < 0 || nx >= size)
                            continue;
                        if (board[ny][nx] == 1 && !discovered[ny][nx]) {
                            discovered[ny][nx] = true;
                            q.push(make_pair(ny, nx));
                        }
                    }
                    ++cnt;
                }
                cntVec.push_back(cnt);
                ++block;
            }
        }
    }
}
 
int main(void) {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%1d", &board[i][j]);
        }
    }
 
    bfs();
 
    printf("%d\n", block);
    sort(cntVec.begin(), cntVec.end());
    int size = cntVec.size();
    for (int i = 0; i < size; ++i) {
        printf("%d\n", cntVec[i]);
    }
}