이 문제는 이것이 코딩테스트다 262페이지 문제이다.
최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다.
이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다.
다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다.
최단경로(다익스트라,플로이드워셜)
최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립
yunzae.tistory.com
아래는 나의 코드이다.
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 |
이 문제는 이것이 코딩테스트다 262페이지 문제이다.
최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다.
이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다.
다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다.
최단경로(다익스트라,플로이드워셜)
최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립
yunzae.tistory.com
아래는 나의 코드이다.
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 |