같은 그룹에 속해있더라도 경로 압축 전엔 부모가 다른 경우가 있습니다.
예를 들어 (2 3) , (1 3)을 순서대로 연결한다고 할 때
(2 3) -> parents[3] = 2 , parents[2] = 2
(1 3) -> parents[2] = 1 , parents[1] = 1
이므로, 여전히 3번 정점의 부모는 2번입니다.
어짜피 MST는 모든 정점이 연결될 수 있는 최소 비용이기 때문에 비용만 비교해도 무방합니다.
16562번 - 친구비
같은 그룹에 속해있더라도 경로 압축 전엔 부모가 다른 경우가 있습니다.
예를 들어 (2 3) , (1 3)을 순서대로 연결한다고 할 때
(2 3) -> parents[3] = 2 , parents[2] = 2
(1 3) -> parents[2] = 1 , parents[1] = 1
이므로, 여전히 3번 정점의 부모는 2번입니다.
어짜피 MST는 모든 정점이 연결될 수 있는 최소 비용이기 때문에 비용만 비교해도 무방합니다.
하지만findParent메서드를 통해 각 부모를 확인하므로
정답 판별 시점엔 모든 경로가 압축되지 않나요?
MST 구성후 parents[] = [0, 0, 1, 2, 3] 과 같이 존재해도
findParent(2) ==> (parents[2] = findParent(1)) ----> (parents[1] = findParent(0)) ----> return 0
처럼 재귀해 정답 판별시점엔 무관하지 않을까 궁금합니다...!
기존 코드에 오타가 있네요. Oh no가 아니라 On no라고 적혀 있습니다.
댓글을 작성하려면 로그인해야 합니다.
jbw9964 1년 전
안녕하세요. 문제 풀이하다 잘 이해되지 않는 부분이 있어 질문 올립니다.
기본 아이디어 :
- 이준석 학생을 정점으로 갖는 MST 구성했을 때, 간선들의 총합이 모든 학생을 친구로 만드는데 필요한 최소 비용일 것이다.
- 이준석 학생을 index=0 인 정점으로 생각하고, 입력으로 주어진 친구비용을 가중치로 갖는 N 개의 간선을 구성.
```
{(준석) ----> (학생 A), 비용 A},
{(준석) ----> (학생 B), 비용 B},
...
```
- MST 구성 후 간선 가중치 합이 K 를 넘거나 모든 정점이 이어지지 않았으면 `Oh no` 출력. 그렇지 않으면 가중치 합 출력.
위 아이디어를 바탕으로 아래와 같은 코드를 만들었습니다.
하지만 채점하니 틀렸었고 여러 방식을 시도하다 아래 코드는 성공하는 것을 발견했습니다.
이 둘의 차이가 뭘까요..?