Inflearn Community Q&A
asked
Union&Find vs DFS
Written on
·
341
4
안녕하세요 강사님.
저는 강의를 듣기 전 이번 문제를 인접리스트를 만든 후 DFS를 이용해서 풀었습니다.(66번 경로탐색 처럼)
두 경우 모두 테스트케이스를 통과하였습니다.
혹시 시간이나 메모리 효율성을 고려했을 때 어느 방법을 선택하는 것이 더 좋을지 알 수 있을까요?
코테 준비 같이 해요! C++
Answer 2
2
codingcamp
Instructor
안녕하세요^^
사실 이문제는 78번 그루스칼 알고리즘을 설명하기 위해 워밍업 문제로 만든 것 뿐입니다.
이 문제의 경우 친구인지 판별하는 쌍이 하나 뿐이라 DFS로 해도 별 차이가 없지만 대부분 이런 스타일의 문제를 만들때는 친구인지 판별하는 질문이 M개를 물어봅니다. 보통 M은 100이상이 들어옵니다. 그럴때는 유니온앤파인드로 풀어야 합니다.
0
