Maximum Total Importance of Roads

요즘 계속 백준 문제들만 풀다가 오랜만에 리트코드 문제를 좀 봤다. 해당 문제는 매주 주말마다 나오는 컨테스트 문제들중 괜찮아 보여서 풀어보기로 했다.

n이라는 노드가 주어지고 roads 가 있을때 각 노드에 가중치 (weights) 를 임의로 줘서 roads 에 적힌 순서대로 탐색을 하고 가중치를 더해줬을때 가장 큰 값을 리턴하면 되는 문제이다. 솔직히 그림만 보고 문제 내용만 보더라도 탐색 문제인줄 알고 가장 먼저 그래프 간선을 만들어주었다. 그런 과정에서 어떻게 하면 임의에 가중치를 내가 줄 수 있을까 생각하던 중에 보니깐 가장 많이 접점이 많은 노드한테 가장 높은 숫자를 주고 그 밑으로 쭉 가중치를 내려주면 마지막 탐색이 끝났을때 더한 값이 가장 크단걸 알게되었다.

그런데 코드를 쓰는 와중에도 느낀건데 이건 탐색 문제가 아닌 그저 그리디와 정렬 문제였다. 애초에 그래프 자체가 필요없는게 느껴져서 과감히 DFS 적은것을 빼고 가중치 순서를 정해준다음에 roads 를 읽어 더 해주었다. 가중치는 Map을 이용해서 저장해주었고 다 풀고보니깐 쉬운문제였다.

그런데 문제와는 별개로 느낀점이 나 그래프 탐색하는 방법을 좀 오래되서 약간 까먹은 느낌이다..? 그래서 내일이나 다른날에 그래프 문제를 풀어볼 생각이다.

배운점:
1. 그림에 속지말자
2. 그리디와 정렬의 연관성