그래프 탐색

DFS,BFS 뼈대 코드

//DFS 뼈대코드
//스택을 이용
bool visited[N];
vector<int> graph[N];

void dfs(int x) {
    visited[x] = true;
    for (int i = 0; i < graph.size(), i++) {
        int y = graph[x][i];
        if (!visited[y])
            dfs(y);
    }
}

//BFS의 뼈대 코드
//Queue를 이용
#include <queue>

bool visited[N];
vector<int> graph[N];

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

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            q.push(y);
            visited[y] = true;
        }
    }
}

• 직접적인 그래프 탐색

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

• 경로 찾기형 문제

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

• https://www.acmicpc.net/problem/1325

• https://www.acmicpc.net/problem/13549

• 행렬 응용문제

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

• https://www.acmicpc.net/problem/14940

• https://www.acmicpc.net/problem/5547