유형별 문제풀이 tony - 분리집합, 동빈북-기타알고리즘이론

백준 1976번 여행 가자 골드5

• 문제
• 코드

파이썬으로 처음에 풀었을 때 여행 정보들을 담아서 다음 여행지로 갈 수 있는지에 대한 체크를 하나하나씩 해줬다 a-b-c-d라면 a,b 에 대해 각각 find_parent()를 해서 둘이 같은지를 비교하는 방식. 그 다음 b-c비교

다른 분들 풀이를 보고 그럴 필요 없이 어차피 연결되어 있다면 한 노드에서의 parent만 비교해도 되므로(어차피 루트 노트가 다 같을 것)
맨 첫번째의 여행지의 root를 저장해 두고 다음 여행지마다 루트 여행지가 저장해둔 root여행지인지 확인하는 것으로 수정했다.