문제 링크

프로그래머스 문제

풀이

최소의 경로를 찾아아 했기에 BFS를 이용해서 풀어야 겠다는 생각이 들었다.
아래와 같은 생각의 과정을 거쳤다.

• 각 노드에 가중치가 부여된 트리가 있다,
• 연산과정을 통해 0을 만드는 것이 목표다
• 두 점을 연결하여 1을 증가시키고 한쪽은 1감소시킵니다.
• 최소한의 행동을 하자
• 불가능하다면 -1을 반환
• 처음 생각한 방법은 DFS로 완전탐색으로 찾는것,
• 하지만 연결된 길이의 개수가 너무 많다.

하지만 풀지 못해 , longroadhome님의 풀이를 참고하게되었다. 풀이중 iterative 한 bfs를 사용하는 과정이 있는데 이를 사용하였다.
특이한 점은 while문 내부에서 queue를 pop해주는 것이다. 일반적으로 queue를 사용하기 때문에 최근에 사용한 것을 바로 반환해 주었지만 일부 dfs 와 같은 방향처럼 진행하던 가장 최근의 행동을 한번더 수행하기 위해서 이다.
또한 answer의 크기가 굉장히 커지므로 Big int를 사용하게 되었다.

코드

function solution(a, edges) {
	const graph = new Array(a.length).fill(0).map(() => new Array());
	for (const [u, v] of edges) {
		graph[u].push(v);
		graph[v].push(u);
	}
	const visit = new Array(a.length + 1).fill(false);

	const queue = [[0, -1]]; //

	let answer = 0n; // 여기가 Big int를 사용한 지점
	while (queue.length) {
		const [curNode, parent] = queue.pop();

		if (visit[curNode]) {
			a[parent] += a[curNode];
			answer += BigInt(Math.abs(a[curNode]));
			continue;
		} else {
			queue.push([curNode, parent]);
			visit[curNode] = true;

			for (let i = 0; i < graph[curNode].length; i++) {
				const nextNode = graph[curNode][i];
				if (!visit[nextNode]) {
					queue.push([nextNode, curNode]);
				}
			}
		}
	}

	return a[0] ? -1 : answer;
}

// 각 노드에 가중치가 부여된 트리가 있다,
// 연산과정을 통해 0을 만드는 것이 목표다
// 두 점을 연결하여 1을 증가시키고 한쪽은 1감소시킵니다.
// 최소한의 행동을 하자
// 불가능하다면 -1을 반환
// 처음 생각한 방법은 DFS로 완전탐색으로 찾는것,
// 하지만 연결된 길이의 개수가 너무 많다.