c++/ 자료구조&알고리즘 개념 복습하기 - 9 / DFS & 사이클 찾기

< DFS >

• 다차원 배열에서 각 칸을 방문하는 경우 깊이를 우선으로!
• 스택을 주로 사용한다
• 재귀로도 가능

#include <stdio.h>
#include <vector>

using namespace std;

const int MAX = 100;

 
int n, m;
vector <int> myGraph[MAX];
bool visited[MAX];

void DFS(int x){
  // x노드 부터 시작하는 dfs 하여 그 순서를 출력하는 함수
  // visited 배열에 방문 기록
  
  visited[x] = true; // 방문 처리 해주기!!
  printf("%d ", x); // 방문한 노드x를 출력
  
  for(int i = 0; i < myGraph[x].size(); i++){
    int y = myGraph[x][i];
    
    if(visited[y] == false){
      DFS(y); // 방문을 안했다면 해당 정점으로 간다
    }
  }
}

int main() {

  //노드 수 9   간선 수 12
  //간선
  //1 2
  //1 3
  //2 3 
  //2 4
  //2 6
  //3 7
  //4 5
  //4 7
  //4 8
  //5 6
  //7 8
  //8 9
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
  }
  
  DFS(1);
  
  return 0;
}

출력 = 1 2 3 7 4 5 6 8 9

< 무방향 그래프에서 사이클 찾기 >

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> node[10005];
int visited[10005] = {0};
vector<int> cycle;
int findNode;

int N;

void solve(int curNode, int parentNode)
{   
    cout << "curNode : " << curNode << ", parentNode : " << parentNode << "\n";

    if(visited[curNode] == 1) { // 방문했던 노드 재방문 시 (사이클 시작지점)
        findNode = curNode;
        cycle.push_back(curNode);
        cout << "find : " << findNode << "\n";
        return;
    }
    
    visited[curNode] = 1;

    for(int i = 0; i < node[curNode].size(); i++) {
        int nextNode = node[curNode][i];
        cout << "curNode : " << curNode << ", nextNode : " << nextNode << "\n";

        if(nextNode == parentNode) // 현재 노드 오기 전 방문한 노드로는 가지 않는다
            continue;
        solve(nextNode, curNode);

        if (findNode == -1)
        {
            return; // 사이클 찾았음
        }

        if(findNode == curNode) { // 사이클 시작 지점으로 돌아옴
            findNode = -1;
            return;
        }

        if (findNode >= 1) // 사이클 순회 중
        {
            cycle.push_back(curNode);
            return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++) // 노드 번호는 1부터 시작한다고 가정
    {
        int a, b;
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }

    for(int i = 1; i <= N; i++) { // 그래프 형태 출력
        cout << i << ": ";
        for(int j = 0; j < node[i].size(); j++) {
            cout << node[i][j] << ", ";
        }
        cout << "\n";
    }
    cout << "//////////\n";

    findNode = 0; // 사이클 찾는 순간 -1 값 저장 예정
    solve(1, 1);

    sort(cycle.begin(), cycle.end());

    cout << "사이클 길이 : " << cycle.size() << "\n";
    cout << "사이클 원소 : \n";
    for (int i = 0; i < cycle.size(); i++)
    {
        cout << cycle[i] << " ";
    }

    return 0;
}

// 출력
5
5 2
2 4
4 3
3 1
1 2
1: 3, 2, 
2: 5, 4, 1, 
3: 4, 1, 
4: 2, 3, 
5: 2, 
//////////
curNode : 1, parentNode : 1
curNode : 1, nextNode : 3
curNode : 3, parentNode : 1
curNode : 3, nextNode : 4
curNode : 4, parentNode : 3
curNode : 4, nextNode : 2
curNode : 2, parentNode : 4
curNode : 2, nextNode : 5
curNode : 5, parentNode : 2
curNode : 5, nextNode : 2
curNode : 2, nextNode : 4
curNode : 2, nextNode : 1
curNode : 1, parentNode : 2
find : 1
사이클 길이 : 4
사이클 원소 : 
1 2 3 4