10216번 - Count Circle Groups
문제를 풀다가 도저히 이해가 안되는 부분이 있어서 질문 드립니다.
Union 함수에서
parent[x] = y; 라고 하면 맞는 정답이지만
parent[y] = x; 라고 하면 틀린 답이 됩니다.
답이 틀려질 이유가 있을까요?
틀린 코드에서 77번째 줄의 <를 <=으로 바꾸면 맞네요.
맞은 코드는 우연히 맞은거였군요. 사랑합니다.
우연은 아닌 것 같습니다. 67번째 줄에서 Union을 호출할 때 항상 y가 인덱스가 큰 쪽이 되기 때문에, parent[x] = y; 라는 문장에서 parent[n]의 값이 달라지는 일이 발생하지 않게 됩니다. 그래서 처음에 초기화한 그대로 parent[n]은 n으로 남아있어 문제가 되지 않습니다.
댓글을 작성하려면 로그인해야 합니다.
vvv3334 5년 전
문제를 풀다가 도저히 이해가 안되는 부분이 있어서 질문 드립니다.
Union 함수에서
parent[x] = y; 라고 하면 맞는 정답이지만
parent[y] = x; 라고 하면 틀린 답이 됩니다.
답이 틀려질 이유가 있을까요?