1260)DFS와 BFS

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

DFS 조지는 중이라 DFS만 쓴다.

그래프의 크기와 간선에 대한 정보가 주어졌을 때 

그래프를 DFS로 노드를 방문한 순서와 BFS로 방문한 순서를 각각 출력해야 한다.

지금은 DFS를 공부중이니 DFS로 풀어낸 방법을 복습겸 적는다.

우선 주어진 입력 중 노드의 갯수 n으로 인접행렬의 크기를 설정한다.

그리고 방문 여부를 결정하는 visited 배열을 n 크기만큼 할당받는다.

이후 노드간 연결 정보를 차례대로 입력받는다 무방향 그래프이기 때문에 <u,v>,<v,u> 모두 연결됬음을 표시해야 한다.

그래프 입력이 완료되면 DFS를 수행한다.

DFS는 인접행렬 graph와 visited, 시작점 s를 넘겨 받고 그래프를 순회한다.

graph에서 s에 접근한 뒤 인접 노드 i가 연결되어 있는 지 확인하고 연결되어 있다면 방문하지 않았는 지 확인한다.

노드가 연결되어 있고 방문하지 않았다면 시작점 i를 넘겨주고 DFS를 수행한다.

#include<iostream>
using namespace std;
 
void dfs(bool **graph,bool *visited, int n, int s) {
    visited[s] = true;
    
    cout << s + 1 << endl;
    for (int i = 0; i < n; i++) {
        if (graph[s][i] && !visited[i]) dfs(graph, visited, n, i);
    }
}
 
int main() {
    int n, m, s;
    int u, v;
    bool **graph;
 
    cin >> n >> m >> s;
    graph = new bool*[n];
    for (int i = 0; i< n;i++) {
        graph[i] = new bool[n];
        for (int j = 0; j < n; j++) graph[i][j] = false;
    }
    for (int i = 0; i < m;i++) {
        cin >> u >> v;
        u = u - 1, v = v - 1;
        graph[u][v] = true;
        graph[v][u] = true;
    }
 
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++) visited[i] = false;
 
    s = s - 1;
    dfs(graph,visited, n, s);
 
    system("pause");
    return 0;
}