1717번 - 집합의 표현
main 함수에서 부모가 서로 같은지 체크 하는 부분에서 아래 코드와 같이
if (parent[a] == parent[b]) cout << "YES" << '\n';
이렇게 하면 오답이 나고
int aParent = findParent(a); int bParent = findParent(b); if (aParent == bParent) cout << "YES" << '\n';
이렇게 하면 정답이 되는데 왜 이런 차이가 발생하는지 모르겠습니다. unionParent 하면서 어차피 경로 압축이 일어났기 때문에 또 findParent를 할 필요가 없는 것이라 생각했는데 제가 놓치고 있는 것이 있을까요?
2,3을 합치고
1,2를 합친 상태에서 parent 배열의 값이
1,1,2이기 때문입니다.
findParent(3)을 해주어야 1,1,1으로 부모가 갱신됩니다.
댓글을 작성하려면 로그인해야 합니다.
lisagamer 2년 전
main 함수에서 부모가 서로 같은지 체크 하는 부분에서 아래 코드와 같이
if (parent[a] == parent[b])
cout << "YES" << '\n';
이렇게 하면 오답이 나고
int aParent = findParent(a);
int bParent = findParent(b);
if (aParent == bParent)
cout << "YES" << '\n';
이렇게 하면 정답이 되는데 왜 이런 차이가 발생하는지 모르겠습니다. unionParent 하면서 어차피 경로 압축이 일어났기 때문에 또 findParent를 할 필요가 없는 것이라 생각했는데 제가 놓치고 있는 것이 있을까요?