Programming/Problem Solving
[Programmers] 모두 0으로 만들기
징석
2021. 7. 25. 11:17
728x90
https://programmers.co.kr/learn/courses/30/lessons/76503
코딩테스트 연습 - 모두 0으로 만들기
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한
programmers.co.kr
이 문제는 처음에는 진짜 트리를 구성해야하나? 이런식으로 고민을 많이 했다.
하지만 생각해보니 무조건 한쪽 끝에서 시작을 하면 되는거였다!!
그래서 inDegree 가 1인 , 즉
이 그림에서 보면 원에서 선이 한 개만 빠져나가는 것들을 모두 Queue에 풀었다! 위상정렬이라고 해야하나..?
처음 queue에 1번, 2번 , 4번 을 넣은 뒤 차례로 꺼내가면서 숫자를 뒤에 더하기/빼기를 해주고 그부분을 다시 queue에 넣으면 된다!
visit도 체크를 하니.. 다시 방문할 일은 없을듯
from collections import deque
def solution(a, edges):
ed = [set() for _ in range(len(a))]
visit = [False]*len(a)
if sum(a) != 0:
return -1
for i in edges:
ed[i[0]].add(i[1])
ed[i[1]].add(i[0])
q = deque()
cnt = 0
for i in range(len(ed)):
if len(ed[i]) == 1:
q.append(i)
while q:
front = q.popleft()
if len(ed[front]) == 0:
continue
temp = ed[front].pop()
if a[front] != 0:
cnt += abs(a[front])
a[temp] += a[front]
a[front] = 0
ed[temp].remove(front)
if len(ed[temp]) == 1:
q.append(temp)
return cnt