단절점의 판단에 대한 질문

[yukyeongmin]

아까 줌 때 말한 내용인데
"DFS()의 시작노드일때 시작노드와 연결된 노드수로 단절점을 판단하면 틀린다. "라고 제가 생각한 케이스를 그림으로 보여드리려구요.

그냥 사이클 그래프 인데, 여기서 1을 시작노드로 생각하면,
연결된 노드수가 2이지만 1은 단절점이 아니지 않나 싶어서요.
1을 제거해도 펼쳐질 뿐이지 2개로 쪼개지지는 않잖아요.

은서님은 통과하셨다고 했는데 이 경우에도 되는건가요??
-> 은서님이랑 정훈님이 설명해주셨는데 시작노드에서 방문한적 없는 노드면 child++하면 된다고 하시네요.
-> 저는 방문한적 없는 노드로 판단하면 되겠다고 생각못해서 아예 dfs를 다 돌고 나오는 걸로 생각했네요.

[wjdgns7712]

static int dfs(int id, boolean isRoot, int parent){
        order[id] = cnt++;
        int ret = order[id];
        int child = 0;
        for (int now : tree[id]) {
            if (now == parent) continue;
            
            if (order[now]==0){ // 아직 방문한 적이 없다면 child를 추가!
                child++;
                int low = dfs(now, false, id);
                if (!isRoot && low >= order[id])
                    answer.add(id);
                ret = Math.min(ret, low);
            } else
                ret = Math.min(ret, order[now]);
        }
        if (isRoot && child>=2) // 시작점이고 자식의 수가 2 이상이라면 단절점.
            answer.add(id);
        return ret;
    }

다른건 볼거없을거같고 주석부분만 보시면 될거같아요.

제 생각에는...

dfs함수의 역할자체가 어떤 노드도 방문하지 않은 초기상태의 그래프에서 방문순서 order를 이용해서

cycle을 없애고 tree 형태로 만드는 과정이 포함되어있고, 트리로 만들고 난 뒤의 자식의 수로 판단해야하지 않나 싶어요.

그래서 어떤점이든 시작점으로해서 dfs를 한번 실행하고나면 자연스레 그림에서의 1번점과 6번점의 order가 달라지므로 6번은 1번의 자식으로 처리가 안되는것 같습니다!

아까는 말로 들어서 무슨 말인지 잘 이해가 안됐는데, 이렇게 글로 보니깐 이해가 되네요

[yukyeongmin]

감사합니다 이해됐어요

[wjdgns7712]

근데 이 부분에 대해서는 솔직히 고민해본적이 없이 그냥 무분별하게 받아들였던것같아요. 덕분에 좋은 계기가 된거같아요!