DFS

서론

언제나 그렇지만 첫 문제는 머리가 깨진다. 아무리 해봐도 혼자서는 못풀겠단 생각이 들어 다른 블로그를 보고 알고리즘을 배운뒤에 2번 3번 문제에 적용을 시키곤 한다.
그렇기에 다른사람이 푼 코드와 알고리즘에 대한 계념을 먼저 잡고 시작해보록하자.

DFS 알고리즘 - 계념

DFS(깊이 우선 탐색)이란 모든 노드를 방문하고자 할때 쓰는 알고리즘이며, 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 여기서 백트랙킹의 계념을 쓰게 되는데,
1. 시작노드 방문
2. 인접노드 방문
3. 인접노드를 기준으로 인접노드의 인접노드를 방문

• 쉽게 말해서 그냥 끝까지 가보는 것이다.(깊이를 깊게)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> //memset

using namespace std;
const int MAX = 10000 + 1;
int N, M;
vector<int> graph[MAX];
bool visited[MAX];
int cnt;

void DFS(int nodeNum) {
    visited[nodeNum] = true;
    for (int i = 0; i < graph[nodeNum].size(); i++) {
        int next = graph[nodeNum][i];
        if (!visited[next]) {
            cnt++;
            DFS(next);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 속도 향상 위해
    cin >> N >> M;

    for (int i = 0; i < M; i++) {
        int node1, node2;
        cin >> node1 >> node2;
        graph[node2].push_back(node1);
    }
    int nodeCnt = 0;
    vector<int> result;
    for (int i = 1; i <= N; i++) {
        memset(visited, false, sizeof(visited));
        cnt = 0;
        DFS(i);
        if (nodeCnt == cnt)
            result.push_back(i);
        if (nodeCnt < cnt) {
            nodeCnt = cnt;
            result.clear();
            result.push_back(i);
        }
    }
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
    cout << endl;
    return 0;
}

참고 사이트 https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://jaimemin.tistory.com/656