[구름톤 챌린지] 연합(day 16)

코딩 2023. 9. 4. 15:03

728x90

구름LEVEL

난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.

level.goorm.io

기초 문제 위주로 나오는가 싶더니 이제 본격적으로 공부가 좀 필요한 문제가 나오는 것 같다. 물론 dfs처럼 탐색으로 풀 수도 있겠지만 이번에는 union find를 이용해 보자.

두구두구

오? 얼핏 보면 완벽해 보이지만 이건 정점이 간선 하나로만 연결이 되어도 하나의 집합으로 다 합쳐버리는 잘못된 코드이다. 간선이 단방향이라고 말 안한 내 잘못이 더 크겠지만,, 그 부분을 수정해달라고 하자.

이 정도면 찰떡같이 알아듣겠지..?

오늘도 열심히 일하는 chatgpt였지만 이것 역시 2% 부족하다. (a, b)를 딕셔너리에 넣지도 않았는데 왜 체크하는 거니..

#wrong
if (a, b) in edges and (b, a) in edges:
    union(parent, a, b)
    

#correct
if (b, a) in edges:
    union(parent, a, b)

이렇게 맞게 고쳐주면?

그럼 오늘은 여기서 끝

728x90

using namespace std; using namespace std;