Programmers - 모두 0으로 만들기
title: Programmers - 모두 0으로 만들기
date: 2022-08-05
tags:
- Algorithm
- DFS
https://school.programmers.co.kr/learn/courses/30/lessons/76503
문제 요약
트리가 주어지며 노드가 N개, 노드를 연결하는 간선이 N-1개, 각 노드에는 가중치가 주어진다.
연결된 노드일 경우, 한 쪽은 1을 감소시키고 한 쪽은 1을 증가시킬 수 있다.
모든 노드의 가중치를 0으로 만들 수 없다면 -1을, 가능하다면 해당 작업을 최소 몇 번 진행해야 하는지 return한다.
문제 풀이
노드는 300K, 가중치의 절대값은 1M까지 주어진다.
생각보다 노드의 양이 많아 겁을 먹었으나, 간선의 개수는 노드의 개수보다 1개가 작고 트리 구조인 것이 정해져있기에 알고리즘만 잘 작성하면 문제가 되지 않을 것이라 판단하였다.
하나의 노드에 여러 노드가 연결되어 있을 경우, 어느 방향으로 가야 best인지 지금은 알지 못하기에 모든 방향으로 작업을 해야 한다.
이런 방식으로 진행하면 시간 초과가 나올 것이라 직감하였고, 한 가지 방안을 떠올렸다.
간선의 개수가 1개인 노드는 연결된 노드로 전해주어야만 한다. 그렇기에 가중치를 넘겨주고 해당 간선을 끊는다.
트리이기에 이를 반복하다보면 간선의 삭제로 인하여 간선의 개수가 1인 노드는 항상 존재하며, 결국 하나의 노드에 가중치가 집중이 되어 0이 될 것이다.
간선의 정보는 vector에 담으며, 각 vector는 unordered_map 방식으로 간선을 저장한다.unordered_map이 아닌 vector 방식으로 이용할 경우, 삭제해야 할 간선을 찾아야 하며 erase 작업에도 시간이 소요가 된다.vector는 중간의 삽입 혹은 삭제시 overhead가 크다. 그렇기에 unordered_map을 이용하였다.
이후 모든 노드를 순회하며 간선의 개수가 1개라면 가중치 이전 및 삭제 작업을 진행한다.
해당 작업을 마친 후, return하기 전에 이전한 노드의 간선의 개수가 1개가 되면 재귀적으로 호출하여 탐색 시간을 줄인다.
처음에는 괜찮은 알고리즘이라 생각하였으나, 막상 구현을 할수록 알고리즘이 그렇게 좋지 않다는 것을 깨달았다.
단순 조회라면 unordered_map 도입이 좋으나, unordered_map의 원소 삭제에서 overhead가 생각보다 크다.
여기에서도 나와있지만, unordered_map은 내부적으로 선형으로 연결이 되어 있다.vector보다 조금은 빠르겠으나, 그럼에도 원소 탐색, 삭제, 전후를 다시 이어주는 작업이 생긴다.
이보다는 트리라는 점을 적극 이용하는 알고리즘이 훨씬 좋은 성능을 가져올 것 같다.
임의의 노드를 Root로 설정한 후, 최하단의 Leaf 노드에서부터 값을 가져오는 것이다.DFS 방식이라면 가장 깊게 내려간 후, 올라오면서 값을 계속 갱신할 것이며, 해당 노드의 Parent만 무시하면 되므로 간선의 삭제라는 불필요한 작업이 필요하지 않다.
프로그램
#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <utility>
using std :: string ;
using std :: vector ;
using std :: unordered_map ;
using std :: pair ;
using std :: make_pair ;
pair < long long , int > iEraseSingleLine ( vector < unordered_map < int , int > > & vGraph ,
long long * llpNodeWeight , int iTarget ) // If a is the only node that connected to b, then erase 'a to b' line
{ // Return ( process count , erased node count )
long long llProcessCount = 0 ;
int iEraseCount = 0;
auto iter = vGraph [ iTarget ].begin () ;
llProcessCount += labs ( llpNodeWeight [ iTarget ] ) ;
++ iEraseCount ;
llpNodeWeight [ iter -> first ] += llpNodeWeight [ iTarget ] ;
llpNodeWeight [ iTarget ] = 0 ;
vGraph [ iTarget ].clear () ;
vGraph [ iter -> first ].erase ( iTarget ) ;
if ( 1 == vGraph [ iter -> first ].size () ) // If transfered node has only one line, then process recursively
{
pair < long long , int > pTemp = iEraseSingleLine ( vGraph , llpNodeWeight , iter -> first ) ;
llProcessCount += pTemp.first ;
iEraseCount += pTemp.second ;
}
return { llProcessCount , iEraseCount } ;
}
long long solution ( vector < int > a , vector < vector < int > > edges )
{
long long answer = 0 ;
int iNodeSize = a.size () ;
vector < unordered_map < int , int > > vGraph ( iNodeSize ) ;
int iCnt = 0 ;
int * ipNodeWeight = a.data () ;
vector < long long > vWeight ( iNodeSize , 0 ) ;
long long * llpNodeWeight = vWeight.data () ;
for ( int i = 0 ; i < iNodeSize - 1 ; ++i )
{
int * ipTemp = edges [ i ].data () ;
int iStart = * ipTemp ++ ;
int iEnd = * ipTemp ;
++ vGraph [ iStart ] [ iEnd ] ;
++ vGraph [ iEnd ] [ iStart ] ;
answer += * ipNodeWeight ;
llpNodeWeight [ i ] = * ipNodeWeight ++ ;
}
llpNodeWeight [ iNodeSize - 1 ] = * ipNodeWeight ;
if ( 0 != answer + * ipNodeWeight ) // Sum is not 0, then can't make all 0
return -1 ;
answer = 0 ;
for ( int i = 0 ; i < iNodeSize ; ++i )
{
if ( 0 == vGraph [ i ].size () )
++ iCnt ;
}
bool bUpdate = false ;
while ( iNodeSize != iCnt )
{
bUpdate = false ;
for ( int i = 0 ; i < iNodeSize ; ++i )
{
if ( 1 == vGraph [ i ].size () ) // If only one line exist, transfer weight to connected Node
{
pair < long long , int > pUpdate = iEraseSingleLine ( vGraph , llpNodeWeight , i ) ;
answer += pUpdate.first ;
iCnt += pUpdate.second ;
bUpdate = true ;
}
}
if ( ! bUpdate )
break ;
}
return answer ;
}