[Programmers] 모두 0으로 만들기

https://programmers.co.kr/learn/courses/30/lessons/76503

코딩테스트 연습 - 모두 0으로 만들기

 

이 문제는 처음에는 진짜 트리를 구성해야하나? 이런식으로 고민을 많이 했다.

하지만 생각해보니 무조건 한쪽 끝에서 시작을 하면 되는거였다!!

 

그래서 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