https://school.programmers.co.kr/learn/courses/30/lessons/42861
내가 풀고도 놀랐다. 풀 수 있을 줄 몰랐다.
생각의 흐름
딱 읽고 감이 안 와서 문제를 분석해봤다.
예전에는 감이 안 오면 뭔가 조급해지고, 좌절감이 들었었는데
이제는 문제 본문과 예제를(부족하다면 내가 추가해서) 좀 더 구체적으로 확인해보면
자연스럽게 드는 생각들이 도움이 된다는 것을 알게 됐다.
난 멍청이 까지는 아니니까 결국 문제에 적응하는 시간과 다양한 경험(예제)가 필요한 것이라고 생각하게 됐다.
[분석 결과]
1. 본문 내용 구체적으로 읽어보고 파악한 점
- n이 100 밖에 안된다.
2. 예제 따라 가보며 떠오르는 생각 정리하기
- 음... 결국 도달만 가능하면 되는 거네
- 그러면 다익스트라 알고리즘 마냥 일종의 방문해버린 노드와 방문할 노드로 구분할 수 있겠는데
분석해본 뒤에 엣지를 선택하는 기준에 대해서 조금 더 생각해보다가
그 이후의 선택들은 모르겠지만 최소한 "최초로 선택해야할 엣지"는 코스트가 가장 작은 엣지라는 것을 파악하게 되었다.
예를 들어 노드 A, B를 연결하는 엣지 E가 전체 엣지 중 가장 코스트가 낮다고 해보자.
그렇다면 무조건 엣지 E를 선택하는 것이 이득이라는 것을 알 수 있다.
노드 A를 포함하는 그룹인 G(A)와 노드 B를 포함하는 그룹인 G(B)가 있을 때,
이 둘은 결국 특정 엣지를 통해서 연결되어야 하고,
다른 노드 사이의 엣지보다는 E를 통해 연결하는 것이 코스트가 가장 낮아지기 때문이다.
그러면 혹시 계속 작은 엣지를 가져가면 되는건가?라는 생각이 들었다 그리고 그건 맞는 생각이었다.
다익스트라 알고리즘 식으로 생각해보면, 하나의 그룹이 되어버린 노드들을 그냥 하나의 노드라고 가정해버릴 수도 있다.
대신 그러려면 엣지 몇개를 없애줘야 한다.
왜냐하면 그룹에서 다른 특정 노드로의 엣지는 여러 개가 될 수 있기 때문인데,
그 엣지들 중 코스트가 가장 낮은 엣지를 그 그룹(노드라고 가정해버린)에서 특정 노드로의 엣지(일종의 대표 엣지? 정도)라고 봐야한다.
아무튼 그렇게 엣지 중복 문제를 해결해버리면 아래처럼 생각할 수 있다.
노드를 합친 그룹을 그냥 좀 큰 노드로 생각해버리면,
앞서서 살펴본 "최초로 선택할 엣지는 전체 엣지 중 가장 코스트가 작은 엣지"라는 점을 계속 적용할 수 있다.
그러니 결국 계속 코스트가 가장 작은 엣지를 선택하는 것이 정답이 된다.
그런데 그렇게 "노드를 합쳐서 만든 그룹의 엣지"를 구하려면 구현이 쉽지 않다는 것을 알게 되었다.
왜냐하면 그룹에서 특정 노드로의 엣지(대표엣지)를 구하려면 노드를 합칠 때마다
해당 그룹에 속한 노드들의 모든 엣지를 둘러봐야 하기 때문이다.
그렇게 구현에 대해 고민을 하다가 보니,
costs를 엣지 코스트에 대한 오름차순으로 정렬해두고
가장 코스트가 작은 엣지를 살펴볼 때 "시작점과 도착점 노드가 같은 그룹에 속하냐?"만 판단하면 더 쉽게 구현할 수 있다는 생각이 들었다.
그 생각을 하니 머릿속에 어렴풋이 union-find가 스쳐지나갔다.
사실 파이썬으로는 한 번도 구현해본 적이 없었는데, 포인터가 없으니 어떻게 하지 싶긴 했다.
그래서 그냥 대충 list로 구현해버렸는데, 나중에 찾아보니 이게 정석인 것 같았다.
아무튼 그렇게 구현 문제도 해결해서 답을 제출할 수 있었다.
+ union-find 알고리즘에 대해서 시간복잡도 같은 걸 좀 더 공부하면 좋을 듯
코드
def solution(n, costs):
groups = list(range(n))
# print(groups)
answer = 0
costs.sort(key=lambda x:x[2])
for s, e, c in costs:
if checkEnd(groups):
break
if checkSameGroup(groups, s, e):
continue
answer += c
merge(groups, s, e)
# print(answer)
return answer
def findParent(groups, num):
ret = -1
nn = groups[num]
while True:
if nn == groups[nn]:
ret = nn
break
nn = groups[nn]
return nn
def merge(groups, a, b):
parentA = findParent(groups, a)
parentB = findParent(groups, b)
if parentA > parentB:
groups[parentA] = parentB
else:
groups[parentB] = parentA
def checkSameGroup(groups, a, b):
parentA = findParent(groups, a)
parentB = findParent(groups, b)
return parentA == parentB
def checkEnd(groups):
for g in groups:
if g != 0:
return False
return True
'알고리즘' 카테고리의 다른 글
| 백준 9252 : LCS (0) | 2024.11.05 |
|---|---|
| 백준 2217 : 로프 (2) | 2024.10.12 |
| 백준 1026 : 보물 (1) | 2024.10.12 |
| 백준 1931 : 회의실 배정 (1) | 2024.10.09 |
| 백준 1193 : 분수찾기 (0) | 2024.10.08 |
