TIL (2022/02/25)

TIL 2가지 (c++ 기준)

(1) 백준 1260번 : DFS와 BFS

#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001
 
int N, M, V;
int graph[MAX][MAX]; 
bool visited[MAX]; 
queue<int> que;
 
void init() {
    for (int i = 1; i <= N; i++) {
        visited[i] = false;
    }
}
 
void dfs(int v) {
    visited[v] = true;
    cout << v << " ";
    
    for (int i = 1; i <= N; i++) {
        if (graph[v][i] == 1 && !visited[i]) { 
            dfs(i);
        }
    }
}
 
void bfs(int v) {
    que.push(v);
    visited[v] = true;
    cout << v << " ";
 
    while (!que.empty()) {
        int first = que.front();
        que.pop();
        
        for (int i = 1; i <= N; i++) {
            if (graph[first][i] == 1 && !visited[i]) { 
                que.push(i);
                visited[i] = true;
                cout << i<< " ";
            }
        }
    }
}
 
int main() {
    cin >> N >> M >> V;
 
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }
 
    init();
    dfs(V);
    
    cout << endl;
    
    init();
    bfs(V);
 
    return 0;
}

(2) 백준 2252번 : [줄 세우기]

위상정렬을 사용하는 문제
-> 순서가 정해져 있는 작업을 수행할 때, 그 순서를 정해주는 것.
방법 1. 해당 노드에 접근하기 전에 먼저 접근해야하는 노드의 수를 기록하고 bfs로 출력 (<- 내가 선택한 방법)
방법 2. dfs로 돌리고 순서대로 stack에 집어넣고 빼는 방법.

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

int N;
int M;

vector<int>students[32001];
int degree[32001];

void bfs(){
// 위상이 0인 정점들 넣는 큐 
    queue<int> que;
    for(int i=1;i<=N;i++){
    // 위상이 0인 정점을 큐에 넣는다.
        if(degree[i]==0){
            que.push(i);
        }
    }
    while(!que.empty()){
        int x = que.front();
        que.pop();
        
        cout<<x<<" ";
        for(auto nx : students[x]){
            degree[nx]--;
            if(degree[nx]==0){
                que.push(nx);
            }
        }
    }
}

int main(){
    cin>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        cin>>x>>y;
        students[x].push_back(y);
        degree[y]++;
    }
    bfs();
}