vvv3334   2년 전

문제를 풀다가 도저히 이해가 안되는 부분이 있어서 질문 드립니다.

Union 함수에서

parent[x] = y; 라고 하면 맞는 정답이지만

parent[y] = x; 라고 하면 틀린 답이 됩니다.

답이 틀려질 이유가 있을까요?

djm03178   2년 전

틀린 코드에서 77번째 줄의 <를 <=으로 바꾸면 맞네요.

vvv3334   2년 전

맞은 코드는 우연히 맞은거였군요. 사랑합니다.

djm03178   2년 전

우연은 아닌 것 같습니다. 67번째 줄에서 Union을 호출할 때 항상 y가 인덱스가 큰 쪽이 되기 때문에, parent[x] = y; 라는 문장에서 parent[n]의 값이 달라지는 일이 발생하지 않게 됩니다. 그래서 처음에 초기화한 그대로 parent[n]은 n으로 남아있어 문제가 되지 않습니다.

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