1949번 - 우수 마을
정점 가중치가 0보다 크기 때문에, 임의 정점에 대하여 어떠한 우수 마을도 인접하지 않는 경우는 없습니다.
조건 1에 따르면, 어떤 정점 v가 우수 마을이 아니고 v와 인접한 모든 정점들 w 역시 우수 마을이 아닌 상태라면, v를 추가로 우수 마을로 선정할 수 있기 때문입니다.
따라서 각 w 서브 트리들에서 w를 선정하지 않은 경우가 선정한 경우보다 더 큰 경우가 된다면, 이들을 포함한 v 서브 트리에서는 무조건 v를 우수 마을로 선정한 것이 그렇지 않은 경우보다 크게 됩니다.
따라서 조건 3은 자동으로 따라오는 성질입니다.
감사합니다 근데 만약 정점 가중치가 음수인 경우도 있어서 조건3을 따로 체크를 해줘야한다면 코드로 어떻게 구현해야 되나요??
어떻게 구현이 가능한지 감이 전혀 안잡힙니다.
댓글을 작성하려면 로그인해야 합니다.
canplane 3년 전 4
정점 가중치가 0보다 크기 때문에, 임의 정점에 대하여 어떠한 우수 마을도 인접하지 않는 경우는 없습니다.
조건 1에 따르면, 어떤 정점 v가 우수 마을이 아니고 v와 인접한 모든 정점들 w 역시 우수 마을이 아닌 상태라면, v를 추가로 우수 마을로 선정할 수 있기 때문입니다.
따라서 각 w 서브 트리들에서 w를 선정하지 않은 경우가 선정한 경우보다 더 큰 경우가 된다면, 이들을 포함한 v 서브 트리에서는 무조건 v를 우수 마을로 선정한 것이 그렇지 않은 경우보다 크게 됩니다.
따라서 조건 3은 자동으로 따라오는 성질입니다.