11724번 - 연결 요소의 개수
공부하면서 visited_edge와 같은 불필요한 부분이 있다는 것과 is_new_continent를 통해 cnt를 증가시키는 시점도 일반적인 그래프 순회와 다름을 배웠습니다.
그런데 제 코드가 아직도 왜 "틀린지"는 모르겠습니다.
cnt가 증가되는 시점과 관련하여 문제라고 ChatGPT는 그랬는데 잘 이해가 안가더군요..
제 cnt가 증가되는 시점은 다음과 같습니다.
DFS로 노드들을 순회하는데 순회하는 노드의 이웃 노드들 중 어떤 것도 방문한 적이 없는 경우 이는 새로운 연결요소로 인지하여 cnt를 증가합니다.
즉, 연결요소가 2개 있다면 각 연결요소의 첫 순회 노드에서 cnt가 증가되는 것입니다.
일단 질문 게시판의 모든 반례들을 테스트해보았는데도 제 정답에 이상이 없어서 질문을 남깁니다.
제 궁금증을 해결해주시면 정말 감사하겠습니다.
와 감사합니다 ㅠㅠ 해결했네요
댓글을 작성하려면 로그인해야 합니다.
jyhan0625 1년 전 1
공부하면서 visited_edge와 같은 불필요한 부분이 있다는 것과 is_new_continent를 통해 cnt를 증가시키는 시점도 일반적인 그래프 순회와 다름을 배웠습니다.
그런데 제 코드가 아직도 왜 "틀린지"는 모르겠습니다.
cnt가 증가되는 시점과 관련하여 문제라고 ChatGPT는 그랬는데 잘 이해가 안가더군요..
제 cnt가 증가되는 시점은 다음과 같습니다.
DFS로 노드들을 순회하는데 순회하는 노드의 이웃 노드들 중 어떤 것도 방문한 적이 없는 경우 이는 새로운 연결요소로 인지하여 cnt를 증가합니다.
즉, 연결요소가 2개 있다면 각 연결요소의 첫 순회 노드에서 cnt가 증가되는 것입니다.
일단 질문 게시판의 모든 반례들을 테스트해보았는데도 제 정답에 이상이 없어서 질문을 남깁니다.
제 궁금증을 해결해주시면 정말 감사하겠습니다.