인프런 커뮤니티 질문&답변

안녕하세요 상민님 ㅎㅎ

지금 보시면

    for(int there : arr[here]) {
        if(visited[there]) continue;
        table[there] = dfs(there);
        cnt += table[there];
    }

해당 노드로 부터 뻗어나가는 노드의 table에 담으신 거잖아요.

아마 그렇게 해서 dfs를 줄이는 방법을 생각하신 거 같은데요.

생각은 너무나도 좋습니다. ㅎㅎ

다만

2 -> 1 -> 3 -> 4 -> 1

이렇게 되었을 때

1부터시작하게 되면.

table 1 : 3

table 3 : 2

table 4 : 1

이렇게 되겠죠?

근데 사실은 이게 정답이죠.

table 1 : 3

table 3 : 3

table 4 : 3

이러한 반례 때문에 틀린 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.