1. 도시 간 우편 보내기
N개의 도시가 있고, 각 도시는 다른 도시로 우편을 보내고자 한다.
단 X라는 도시에서 Y라는 도시로 전보를 보낸다고 할 때는 반드시 거쳐가는 통로가 존재해야 한다.
어느날 C라는 도시에서 위급상황이 발생하여, 최대한 많은 도시로 최대한 빠르게 보내고자 한다.
이때 도시C로부터의 우편을 받은 도시의 개수와, 메시지를 받기까지 걸린 총 소요시간은을 구하는 알고리즘은?
행, 열의 입력이 아니라, 노드개수와 간선개수에 따른 입력도 어떻게 구성되는지 파악하고 적용한다.
#첫째줄에 도시개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C가 주어진다.
#둘째줄부터 M+1번째 줄에 걸쳐 통로에 대한 정보 X, Y, Z(X에서 Y까지, 걸리는 시간Z)가 주어진다.
#첫째줄에 도시 C에서 받는 도시의 총 개수, 총 걸리는 시간이 공백으로 구분되어 출력된다.
##key point : 한 도시에서 다른 도시까지의 최단거리, 다익스트라.
##시간소요를 최소화하기 위해 우선순위 큐(min heap)을 사용.
import heapq
import sys
INF = int(1e9)
#노드 개수, 간선 개수, 시작 노드
n, m, start = map(int, sys.stdin.readline().split())
#편의성을 위해 index 1~n까지 구성되도록 설정
graph = [[] * (n+1) for _ in range(n+1)]
#최단거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
#간선 정보의 입력
for _ in range(m):
x, y, z = map(int, sys.stdin.readline().split())
#graph에 저장되는 정보는 x에서 y로 가는 비용이 z(최초비용)
graph[x].append((y,z))
def dijkstra(start):
q = []
#최초 시작노드에서 시작
#거쳐가는 노드로 설정하여 거리를 0으로 최초 선언
#heap에 저장되는 정보는 (최단거리, 끝 지점)
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
#heap에서 나온 것은 각 단계에서 노드까지 최단거리로 이미 정해짐
dist, now = heapq.heappop(q)
#dist 값이 초기화된 distance값보다 크면 반복진행하지 않음
#이 의미는 visited 의미를 가지고 있음(방문노드 생략)
if distance[now] < dist:
continue
for i in graph[now]:
#now가 거쳐가는 노드, i가 인접노드
cost = dist + i[1] #i가 인접노드에 대한 정보, 첫번째 값이 비용
if cost < distance[i[0]]: #cost: 거쳐가는 비용 / distance : 다이렉트
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
#알고리즘 수행
dijkstra(start)
#결과값
count = 0
max_distance = 0
for d in distance:
#도달할 수 있는 노드
if d != INF:
count = count + 1
max_distance = max(d, max_distance)
#출력할때 시작노드는 제외
print(count-1, max_distance)
#3 2 12. K회사를 거쳐 X회사로 갈때 소요되는 최소 시간
1번부터 N번까지의 빌딩이 있고, 서로 도로를 통해 연결되어있다.
A라는 사람이 1번 회사에 위치해 있고, X번 회사에 방문 후 물건을 판매하고자 한다.
X번 회사에 방문 후 K번 회사에 방문하여 소개팅까지 진행한다.
각 빌딩은 양방향 이동이 가능하고, 1만큼의 시간이 소요된다.
1번회사에서 출발하여 K번 회사에 방문, X번 회사로 가고자 할 때
회사 사이를 이동하면서 걸린 최소 소요시간을 구하는 알고리즘은?
- 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 제시된다.
- 각 N, M은 1~100사이의 양의 정수이다.
- 둘째 줄부터 M+1번째 까지 연결된 두 회사의 번호가 공백으로 주어진다.
- M+2번째 줄에는 X와 K 공백으로 주어진다.
- A가 K를 거쳐 x로 이동하는 최소 이동시간을 출력하고, 이동 불가 시 -1을 출력한다.
역시 행, 열의 입력이 아닌, 노드개수 - 간선개수의 입력이 필요함에 유의하며, 각각 입력하는 단계도 누락없이 잘 구성할 수 있도록 대비한다.
※ 거쳐간다, 노드의 개수가 100개이므로 플로이드-와샬을 적용한다면 효율적인 방안이 될 수 있다.
##노드의 선택 기준이 거쳐가는 노드로, 전형적인 플로이드 와샬 구현 유형
##노드가 최대 100이므로, 플로이드 워셜 알고리즘을 이용해도 효율적(*문제 자체가 최단거리)
##플로이드 워셜을 적용한다면 1번노드에서 k까지의 소요시간과 K에서 X까지의 소요시간을 더하면 된다.
import sys
INF = int(1e9)
#노드와 간선의 개수
n, m = map(int, sys.stdin.readline().split())
#2차원 리스트
graph = [[INF] * (n+1) for _ in range(n+1)]
#자기자신에서 자기자신으로 가는 비용은 0
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
#각 간선에 대한 정보 입력
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
#각 행열값은 행에서 열로가는 시간(비용)을 의미
#다익스트라와 마찬가지로, 2중반복이 아닌 간선 개수만큼 반복함에 유의
graph[a][b] = 1
graph[b][a] = 1
#거쳐갈 노드 K와 목적지 노드 X를 입력
k, x = map(int, sys.stdin.readline().split())
#플로이드 와샬
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
#수행결과 출력
distance = graph[1][k] + graph[k][x]
K회사를 거쳐 X회사로 갈때 소요되는 최소 시간
if distance == INF:
print(-1)
else:
print(distance)#1 2 4
#1 3 2
2.
```python
## 2.
```python
#1번부터 N번까지의 빌딩이 있고, 서로 도로를 통해 연결되어있다.
#A라는 사람이 1번 회사에 위치해 있고, X번 회사에 방문 후 물건을 판매하고자 한다.
#X번 회사에 방문 후 K번 회사에 방문하여 소개팅까지 진행한다.
#각 빌딩은 양방향 이동이 가능하고, 1만큼의 시간이 소요된다.
#1번회사에서 출발하여 K번 회사에 방문, X번 회사로 가고자 할 때
#회사 사이를 이동하면서 걸린 최소 소요시간을 구하는 알고리즘은?
#첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 제시된다.
#각 N, M은 1~100사이의 양의 정수이다.
#둘쨰 줄부터 M+1번째 까지 연결된 두 회사의 번호가 공백으로 주어진다.
#M+2번째 줄에는 X와 K 공백으로 주어진다.
#A가 K를 거쳐 x로 이동하는 최소 이동시간을 출력하고, 이동 불가 시 -1을 출력한다.
##노드의 선택 기준이 거쳐가는 노드로, 전형적인 플로이드 와샬 구현 유형
##노드가 최대 100이므로, 플로이드 워셜 알고리즘을 이용해도 효율적(*문제 자체가 최단거리)
##플로이드 워셜을 적용한다면 1번노드에서 k까지의 소요시간과 K에서 X까지의 소요시간을 더하면 된다.
import sys
INF = int(1e9)
#노드와 간선의 개수
n, m = map(int, sys.stdin.readline().split())
#2차원 리스트
graph = [[INF] * (n+1) for _ in range(n+1)]
#자기자신에서 자기자신으로 가는 비용은 0
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
#각 간선에 대한 정보 입력
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
#각 행열값은 행에서 열로가는 시간(비용)을 의미
#다익스트라와 마찬가지로, 2중반복이 아닌 간선 개수만큼 반복함에 유의
graph[a][b] = 1
graph[b][a] = 1
#거쳐갈 노드 K와 목적지 노드 X를 입력
k, x = map(int, sys.stdin.readline().split())
#플로이드 와샬
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
#수행결과 출력
distance = graph[1][k] + graph[k][x]
if distance == INF:
print(-1)
else:
print(distance)
```