모두 0으로 만들기
-
[프로그래머스]모두 0으로 만들기 - JAVA문제풀이/프로그래머스 2021. 6. 8. 11:31
[프로그래머스]모두 0으로 만들기 - JAVA https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 많이 해메였던 문제이다. 모든 정점의 가중치를 0으로 만들려면 필요한 아이디어를 먼저 살펴보자. 모든 가중치의 합이 0이된다. (0이 되지 않으면 애초에 모든 정점의 가중치를 0으로 만들 수 없다) 한 방향으로 탐색을 진행하면서 가중치 연산을 해야 한다. (목적 노드를 하나 정해두고 나머지 리..