728x90
반응형
문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/12978
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이:
import heapq
def solution(N, road, K):
graph = [[] for _ in range(N+1)]
for i in range(len(road)):
u, v, w = road[i]
graph[u].append((v, w))
graph[v].append((u,w)) # 양 방향 이기 때문
dist = [float("inf") for _ in range(N+1)]
dist[1] = 0
print(dist)
hq = []
heapq.heappush(hq,(0,1))
while hq:
cur_w,cur_node = heapq.heappop(hq)
for to_node, to_w in graph[cur_node]:
dis = cur_w + to_w
if dis < dist[to_node] :
dist[to_node] = dis
heapq.heappush(hq,(dis,to_node) )
count = 0
for i in dist[1:]:
if i <= K:
count += 1
return count
print(solution(5, [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]], 3))
백준에 있는 골드 문제와 거의 똑같다
graph = [[] for _ in range(N+1)]
for i in range(len(road)):
u, v, w = road[i]
graph[u].append((v, w))
graph[v].append((u,w)) # 양 방향 이기 때문
dist = [float("inf") for _ in range(N+1)]
dist[1] = 0
[[], [(2, 1), (4, 2)], [(1, 1), (3, 3), (5, 2)], [(2, 3), (5, 1)], [(1, 2), (5, 2)], [(2, 2), (3, 1), (4, 2)]]
[inf, 0, inf, inf, inf, inf]일단 그래프를 만들어서 그래프에 간선지와 가중치를 넣는다.
dist 에는 간선지 까지 드는 가중치중 최솟값을 넣어야하니 일단 최댓값인 inf 로 통일
0에서 0 은 없고
1에서 2는 1점 >>(2,1) 1에서 4는 2점(4,2)
2에서 1은 1점 >> (1,1) 2에서3은 3점(3,3) ,,, 이런식으로
그리고 dist[1] 에는 0 을 넣는다 시작점이기때문
hq = []
heapq.heappush(hq,(0,1))
최솟값을 쓰려면 heapq 를 써서 맨 위(리스트 맨앞)에 최솟값을 올린다
그리고 hq 에 가중치와, 시작점을 넣어줌
while hq:
cur_w, cur_node = heapq.heappop(hq) # cur_w 가중치, cur_node 시작점
for to_node, to_w in graph[cur_node]: # to_node 목적지, to_w 가중치 값
dis = cur_w + to_w # 새로운 가중치는 cur_w + to_w
if dis < dist[to_node]: # 기존것과 비교해서 작으면
dist[to_node] = dis # 작은걸로 최신화
heapq.heappush(hq,(dis,to_node)) # 다시 가중치와, 시작지 최신화
이 부분이 가장 어려운 부분인데 내가 이해한 대로 작성해보겠다..
일단 hq 에 들어간 처음 (0,1) 을 꺼내준다
그러면 포문에서는 그래프[1] 1에서 [(2, 1), (4, 2)] 두개가 뽑아 두개를 돌면서
그럼 to_node 와 to_w 에 그 다음 간선지와, 가중치가 들어가게된다.
현재 가중치는 0점이고 , 1>>2가는건 1점, 1>>4 는 2점이 dis(가중치) 이다
dis(1점, 4점이) dist[2와 4] 에 있는 값보다 작으면 dis 와 다음 목적지인 to_node 를 넘기면서
가중치와, 도착지인 노드를 hq에 푸쉬해준다.
쭉 돌면서 완성해주면 최솟값만 남는다.
반응형
댓글