kde6260   2년 전

입출력 부분과 find는 구글링해서 찾은 정답들과 동일합니다만 union에서 틀린이유를 모르겠습니다ㅜㅜ

테스트케이스를 여럿 넣고 돌려봤는데도 틀린 이유를 찾기 힘드네요

고수님들 답변 부탁드립니다ㅜㅜ

djm03178   2년 전

일단 코드는 항상 실행 가능한 전체를 올려야 합니다. 그래야 다른 사람들도 직접 돌려가면서 해보죠. 게다가 '동일하다'고 하셨지만 정말로 한 글자도 다르지 않은지는 직접 보지 않으면 알 수가 없습니다. 한 글자만 다르게 해도 전혀 반대되는 동작을 하게 만들 수 있는 게 프로그래밍 언어입니다.

코드상으로 봤을 때 if랑 else의 분기를 나눈 게 무의미합니다. p_x == x 라는 조건은 그냥 운 좋게(?) x가 현재 set의 루트인 경우를 말하는 거고 x랑 y가 둘 다 각 set의 루트가 아닐 수도 있습니다. 그리고 이 코드는 x와 y가 이미 같은 set에 속한 경우, 즉 p_x == p_y인 경우 문제가 될 것 같습니다.

jh05013   2년 전

"틀렸습니다" 말고 메모리 초과인데 그냥 코드를 전반적으로 잘못 짜신 게 아닐까요?

kde6260   2년 전

파이썬으로 짰을 때 메모리초과가 나서 C++로 수정해서 제출했습니다.

어느게 루트인지 if문으로 나누는 게 무의미하다는 건 이해하겠으나 아래에 '맞은 함수' 주석을 붙인 union함수에서 rel[p_x]을 1로 갱신시켜야 하는 이유를 아직 잘 모르겠습니다.

(제출했을 때 저 맞은/틀린 함수를 기준으로 통과/실패가 떴습니다.)

p_x = 3, p_y = 4, rel[p_x] = 2, rel[p_y] = 5 라고 했을 때

union(3,4) 가 호출되고 나서

3의 루트는 4이고 rel[4] = 7이 됩니다.

그러고 나서 union(3, 6)을 부를 때  find(3)은 4일테고,

rel[6] += rel[4] 와같이 3의 루트인 4의 rel에만 접근을 하게 되는데, union(3,4)에서 굳이 rel[3] = 1이라고 바꿔줘야 하는 이유를 잘 모르겠네요ㅠㅠ

jh05013   2년 전

rel[p_x] = 1은 없어도 됩니다. 틀린 함수는 p_x == p_y(x와 y가 이미 합쳐진 상태)일 때에도 rel값을 증가시키기 때문에 문제가 됩니다.

kde6260   2년 전

아 그렇군요 답변 감사합니다.

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