-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
Union&Find vs DFS
20.12.06 15:52 작성 조회수 270
3
안녕하세요 강사님.
저는 강의를 듣기 전 이번 문제를 인접리스트를 만든 후 DFS를 이용해서 풀었습니다.(66번 경로탐색 처럼)
두 경우 모두 테스트케이스를 통과하였습니다.
혹시 시간이나 메모리 효율성을 고려했을 때 어느 방법을 선택하는 것이 더 좋을지 알 수 있을까요?
답변을 작성해보세요.
2
김태원
지식공유자2020.12.06
안녕하세요^^
사실 이문제는 78번 그루스칼 알고리즘을 설명하기 위해 워밍업 문제로 만든 것 뿐입니다.
이 문제의 경우 친구인지 판별하는 쌍이 하나 뿐이라 DFS로 해도 별 차이가 없지만 대부분 이런 스타일의 문제를 만들때는 친구인지 판별하는 질문이 M개를 물어봅니다. 보통 M은 100이상이 들어옵니다. 그럴때는 유니온앤파인드로 풀어야 합니다.
0
답변 2