[백준 / BOJ] 10891 Cactus? Not cactus? (cpp)

문제

출처 : https://www.acmicpc.net/problem/10891

10891번: Cactus? Not cactus?

양방향 그래프에서 각 정점에서 시작해 자기 자신으로 돌아오는 사이클이 2개 이상이라면 Cactus가 아니며, 하나 이하라면 Cactus이다. 이 때, 주어진 그래프가 Cactus인지 Not cactus인지 출력하는 문제다.

---

풀이

처음에는 단절점을 찾고, 단절점에 대해 자식 트리가 2개 이상이라면 Not cactus를 출력하게 해줬는데, WA를 맞았고, 조금만 생각해봐도 반례를 찾을 수 있었다.

4 5

1 2

1 3

2 3

2 4

3 4

위 그래프는 단절점이 존재하지 않는데, Not cactus이다.

결론적으로, 이 문제를 푸는데 단절점의 유무는 중요하지 않다고 생각했고, 일반적인 dfs로 사이클을 찾아가며 풀었던 문제다.

 

i번 노드를 방문한 순서를 order라 할때, 이전 노드로 거슬러 올라가지 않고, 자신보다 order가 작은 노드를 방문할 수 있다면, 사이클이 생긴다. 만약 사이클이 생길경우, 이 사이클에 포함되는 노드들에 cycle수를 1씩 증가해주고 최종적으로 2개 이상의 사이클에 포함되어있는 노드가 있다면 Not cactus 아니라면, Cactus를 출력해주면 된다.

 

문제를 풀며 한 사이클에 포함되어있는 노드들과 포함되지 않는 노드들을 판별하는것이 어려웠는데, 오랜 고민끝에, 사이클이 열리는지점에 체크를 해줘서, 재귀가 풀리며 사이클이 열리는 지점으로 돌아왔을때, 체크해준값을 처리해주는 식으로 구현했다. 예를들어, 더 큰 방문 순서를 가진 노드(A) 에서 더 작은 방문 순서를 가진 노드(B) 로 방문하는 경우가 사이클이 열리는 지점이므로, B지점에 돌아왔을때, 사이클을 풀어주기 위해 outDegree[B]++를 해준다. 이 후에 재귀가 풀리며 B지점에 도달했을때, cycle의 수에 outDegree값을 빼주면, B 지점 전의 방문순서를 가진 노드들의 cycle수는 노드 B와 노드 A가 포함된 사이클 수에 영향을 받지않는다.

 

자세한 내용은 코드를 보도록 하자.

outDegree는 사이클이 풀리는 횟수

inDegree는 노드가 포함된 사이클의 갯수이다.

int dfs(int befIdx, int idx){
    if(orders[idx] > 0){
        outDegree[idx]++;
        return 1;
    }
    orders[idx] = order++;
    int cycle = 0;
    for(int i = 0; i < edges[idx].size(); i++){
        int nextIdx = edges[idx][i];
        if(befIdx == nextIdx || orders[nextIdx] > orders[idx]) continue;
        cycle += dfs(idx, nextIdx);
    }
    inDegree[idx] = cycle;
    return cycle - outDegree[idx];
}

사이클 판별 문제를 접해볼 기회가 많지않아서 그런가 사이클 포함유무를 생각해 내는데 오랜 시간이 걸린 문제였다. 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/tree/master/10891%20Cactus%3F%20Not%20cactus%3F

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃