이 문제는 이것이 코딩테스트다 262페이지 문제이다.
최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다.
이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다.
다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다.
아래는 나의 코드이다.
import sys
import heapq
N,M,C=map(int,sys.stdin.readline().split())
INF=int(1e9)
distance=[INF]*(N+1)
graph=[]
for _ in range(N+1):
graph.append([])
for i in range(1,M+1):
temp=list(map(int,sys.stdin.readline().split()))
graph[temp[0]].append((temp[1],temp[2]))
def dijkstra(start):
q=[]
heapq.heappush(q,(0,start))
distance[start]=0
while q:
dist,now = heapq.heappop(q)
if distance[now] <dist:
continue
for next in graph[now]:
next_node=next[0]
next_dist=next[1]+dist
if distance[next_node]>next_dist:
distance[next_node]=next_dist
heapq.heappush(q, (next_dist, next_node))
dijkstra(C)
city_count=0
max_distance=0
for result in distance:
if result!= INF:
city_count+=1
if result>max_distance:
max_distance=result
print(city_count-1,max_distance)
아래는 예시코드이다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수, 시작 노드를 입력받기
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
x, y, z = map(int, input().split())
# X번 노드에서 Y번 노드로 가는 비용이 Z라는 의미
graph[x].append((y, z))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보를 꺼내기
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 노드 중에서, 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
# 도달할 수 있는 노드인 경우
if d != 1e9:
count += 1
max_distance = max(max_distance, d)
# 시작 노드는 제외해야 하므로 count - 1을 출력
print(count - 1, max_distance)
'Problem Solving > 최단 경로' 카테고리의 다른 글
BOJ1916 최소비용 구하기 (0) | 2023.03.30 |
---|---|
BOJ1446 지름길 (0) | 2023.03.21 |
BOJ18352 특정 거리의 도시 찾기 (0) | 2023.03.20 |
미래도시 (0) | 2023.01.19 |