https://programmers.co.kr/learn/courses/30/lessons/76503
코딩테스트 연습 - 모두 0으로 만들기
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한
programmers.co.kr
DFS 문제다. queue로 BFS 풀려했는데 잘 풀리지 않았다
DFS 방식이 좀 친숙해지는 계기가 된 것 같다.
import sys
sys.setrecursionlimit(300000)
answer =0
def solution(a,edges):
global answer
if sum(a) !=0:
return -1
graph = [[] for _ in range(len(a))]
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
def dfs(now,pre):
global answer
for next in graph[now]:
if next != pre:
dfs(next,now)
answer += abs(a[now])
a[pre] += a[now]
a[now] -= a[now]
dfs(0,0)
return answer
'Programming > Programmers' 카테고리의 다른 글
[프로그래머스] 매칭 점수 (Python) (0) | 2021.11.18 |
---|---|
[프로그래머스] 외벽 점검 (Python) (0) | 2021.11.18 |
[프로그래머스] 입양 시각 구하기(2) (MySQL) (0) | 2021.11.17 |
[프로그래머스] 우유와 요거트가 담긴 장바구니 (MySQL) (0) | 2021.11.16 |
[프로그래머스] 헤비 유저가 소유한 장소 (MySQL) (0) | 2021.11.16 |
댓글