Programmers Lv.3 섬 연결하기 #Greedy#탐욕법#Union-Find#Kruskal Algorithm#Graph
[문제]
[접근 방법]
보자마자 최단 거리(최소 비용)를 구하는 문제라고 생각해서 BFS네, 하다가 또 최단 거리 하면 다익스트라인데 하다가, 다익스트라랑은 문제 성격이 좀 달라서 뭐지? 다익스트라 응용인가 하다가
막혀서 찾아보니 크루스컬 알고리즘을 활용하는 문제였다.(매일 매일 모르는 게 나타는 즐거운 매직)
일단 크루스컬 알고리즘은 아이디어가 참 간단한데, 잘 몰라서 헤맸다. 결국 크루스컬 알고리즘은 각 정점을 딱 한 번만 방문하는가 아닌가는 그렇게 중요하지 않다. 간선에 집중하는 알고리즘이다. 주어진 간선의 가중치가 가장 낮은 것부터 확인하면서 start와 end가 같은 부모가 아닌, 즉 사이클이 발생하지 않으면 간선을 포함한다.
여기서 새로운 사실을 하나 안 것은 전에 BOJ문제 풀려고 보다가 분리집합?에 대한 내용이 있어서 처음 Union-Find 문제를 풀고 그 뒤로 한 번도 그 문제를 풀지 않아서 까먹고 있었는데, 이 문제 덕분에 Union-Find가 왜 필요한지, 다익스트라부터 Union-Find까지 오늘 그래프 복습을 제대로 한 날이었다.
그리고 그래프는 강조해도 강조해도 중요하니까 아예 내 공부를 위해서 그래프 파트만 따로 떼서 포스팅을 할 예정이다!!(문제를 풀면서 그래프에 그만 쫄고 그냥 완전 정복을 해버리자는 오기가 생겼다.)
일단 Union-Find는 사이클이 발생했는지 안 했는지 확인해주는 좋은 알고리즘이고, 여기서 중요한 것은 그래프 문제가 나오면 일단 냅다 Node 클래스를 정의해주고 시작하자는 것이 오늘 내가 내린 결론이다.
코드가 좀 길어져도 명확하니까 내가 풀기에는 Set을 쓰고 어쩌고 저쩌고 보다 확실하다. 나같이 이제 처음 알고리즘을 공부하는 사람이라면 코드가 길어져도 그냥 정석대로 다 구현해 보는 것을 추천한다.
막상 풀고 보니 Union-Find 때문에 코드가 길어져서 그렇지 bfs() 자체는 너무 간단하다.
다익스트라와 정말 다른 점은, 다익스트라는 한 정점에서 다른 정점까지 이동하는데 드는 최소 비용을 구하는 것이고, 크루스컬 알고리즘은 모든 노드가 최소 비용으로 연결되기 때문에 사용하는 간선의 수는 결국 (노드개수 - 1)이라는 점이다.
그래서 다익스트라는 우선순위 큐로 각 간선의 가중치를 계속 업데이트 해주기 때문에 결국 모든 정점은 한 번씩만 방문한다. (그 정점까지 가는 데 드는 최소 비용 간선이 게속 우선순위 큐에 쌓이는 것이지, 방문은 결국 한 번만 한다.) 그러나 크루스컬 알고리즘은 “간선”에 집중하는 것이기 때문에 그 간선과 연결된 노드 정보가 필요한 것이지 방문 정보가 필요한 것이 아니다.(visited 배열 필요 없음.)
여기서 중요한 점은 각 노드는 일단 부모 노드가 없으면 자기 자신을 부모 노드로 설정해서 준다는 것이 포인트다. 생각해보니 if(u.parent === null){return u.parent = u} 이 부분만 남겨도 될 거 같다.(이 문제에서는 root가 명시 되어 있진 않기 때문에)
다음에는 아예 DFS/BFS/Daijkstra/Kruskal 문제를 많이 풀고 풀이 비교를 하는 포스팅을 해도 괜찮을 것 같다.