mjun09   10달 전

반례가 떠오르질않네요...

도와주세요 ㅠㅠ

pichulia   10달 전

95번째 줄에서 chk[i] == chk[i+1]을 하는게 맞나요?

열심히 merge를 해놓고 이 정보를 전혀 활용하지 못하고 있습니다

mjun09   10달 전

chk배열로 같은 그래프에 속하는지 여부를 판단하려고 하였습니다!

따라서 chk 배열이 모두 같은값을 가진다면 하나의 그래프가 완성되어 MST가 완성되는 것으로 판단하였고

chk 배열안에서 단 하나라도 다른 값을 가진다면 두 개 이상의 그래프가 되므로 MST가 만들어질 수 없다고 판단하였는데..

혹시 제 생각 중 어느 부분에서 미스가 난건지 좀더 상세히 알려주실수있으신가요? ㅠㅠ

pichulia   10달 전

chk값이 제대로 갱신이 안될것입니다.

chk값이 1인 노드가 5개 있고

2인 노드가 5개 있는데


이 둘을 연결하는 간선이 추가됐으면

chk가 2인 노드들이 '전부' 1로 바뀌는 것을 의도하신거같은데

실제 동작은 그렇지 않을 것입니다...


폰이라서 직접 돌려보지는 못해서 예제는 확인을 못하겠습니다만..

아마 아래의 데이터의 경우 맛이 가지 않을까 싶습니다.

mjun09   10달 전

아 세상에.... 정말 멍청했네요.. ㅠㅠ 감사합니다 덕분에 잘 해결했습니다!

말씀해주신 반례를 해결하도록해서 맞았습니다!

추가적으로 맨처음에 말씀해주신걸 토대로 생각해보니 find 함수를 사용하면 될것같더군요!

멍청하게 parent 배열로 비교하다가 안되는거같아 새로 배열을 만들었었는데.. 감사합니다 :D

댓글을 작성하려면 로그인해야 합니다.