알고리즘_코딩테스트/주간코딩 스터디 (주코스)
(Week7)[Dijkestra] 가장 먼 노드
논곰
2022. 7. 8. 15:07
주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요
소요시간: 30분
1. 문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/49189
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
n개의 노드가 있는 그래프에서 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지 return
2. 접근 방식
- 다익스트라 알고리즘을 활용해 문제를 푼다.
- heapq를 활용해서 우선순위큐를 만든다(해당 문제에서는 우선순위가 크게 중요하지 않아보임(거리가 모두 1임))
- '양방향 노드'라는 것을 기억해야 한다. 5번 노드에서 2번 노드로 가는 입력이 있으면, 2번 노드에서 5번 노드로 가는 입력도 넣어줘야 한다.
3. 코드
import heapq
def solution(N, road, K):
INF = 1e9
graph = [[]for _ in range(N+1)]
distance = [INF] * (N+1)
for road_n in road:
a, b, c = road_n
graph[a].append((b, c))
graph[b].append((a, c))
q = []
distance[1] = 0
heapq.heappush(q, (0, 1))
while q:
dist_a, node_a = heapq.heappop(q)
# 이미 처리된 노드의 경우
if distance[node_a] < dist_a:
continue
for node_b, dist_b in graph[node_a]:
new_dist = dist_a + dist_b
if new_dist < distance[node_b]:
distance[node_b] = new_dist
heapq.heappush(q, (new_dist, node_b)) # cost를 키값으로 정렬이 된다.
return len(list(filter(lambda x: x <= K, distance)))
4. 코멘트
- 다익스트라 알고리즘을 활용해서 쉽게 문제를 풀었지만, 스터디에서 시간복잡도를 봤을 때 (파이썬 분들과 비교해도) 가장 낮았었다. 내 생각에는 해당 문제에서는 크게 필요없는 부차적인 부분이 들어갔기 떄문이라고 생각한다.(예를 들어 INF 거리를 -1로 변경하는 부분 등)
- 그래도 변수명이 직관적이어서 이해가 쉬웠다는 좋은 피드백을 받을 수 있었다.
- INF 대신 파이썬에서는 float('inf')를 활용해 Infnit 변수를 만들 수 있다고 한다. 이걸 활용하면 굳이 변수를 정의하지 않고, 코드를 좀 더 직관적으로 짤 수 있을 것 같다.