[이것이 코딩 테스트다] 전보 with Python

🔒 문제

 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면,도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.
 어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

입력

3 2 1
1 2 4
1 3 2

출력

2 4

✅ 해설

• 모든 지점에서 모든 지점까지 최단 거리를 구해주는 플로이드 워셜 알고리즘 사용
  • 플로이드 워셜 알고리즘은 2차원 배열에 최단 거리 저장
    • n개의 노드가 존재할 때, 아래와 같은 크기의 배열 선언 
    • distance[[INF] * (n+1)] * (n+1) 
  • 다익스트라 알고리즘을 사용해도 상관없음

for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            distance[b][c] = min(distance[b][c], distance[b][a] + distance[a][c])

• 사용자가 입력한 노드와 노드 사이의 거리를 고려하여 distance[][] 배열 초기화

# 시작 노드와 연결 노드 사이 거리로 distance[] 배열 초기화
distance = [[INF] * (n+1)] * (n+1)
for i in range(1, n+1):
    for j in graph[i]:
        distance[i][j[0]] = j[1]

• distance[][]에 모든 최단 거리가 저장됐다면, 나라 c에서 전파될 수 있는 모든 나라의 수를 세야 함
  • 만약 distance[c][i] >= INF라면 도달할 수 없다는 뜻이므로 건너뜀
  • 나중에 distance[c] 배열 중 INF 값을 제외하고 가장 큰 값을 구할 때 편리하도록 INF -> -1로 바꾼다.
  • 아니라면 count 변수 1 증가
• 모든 나라가 메시지를 받는 데 걸리는 시간은 INF를 제외하고 최단 거리가 가장 긴 나라의 최단 거리를 의미한다.
  • distance[c] 배열에서 가장 큰 값을 고르면 됨

💻 코드

INF = int(1e9)

# 도시의 개수 n, 통로의 개수 m, 메시지를 보내고자 하는 도시 c 입력받기
n, m, c = map(int, input().split())

# 통로에 대한 정보 입력받기
graph = [[] for _ in range(n+1)]

for i in range(m):
    start, end, dist = map(int, input().split())
    graph[start].append((end, dist))

# 시작 노드와 연결 노드 사이 거리로 distance[] 배열 초기화
distance = [[INF] * (n+1)] * (n+1)
for i in range(1, n+1):
    for j in graph[i]:
        distance[i][j[0]] = j[1]

# 플로이드 워셜 알고리즘
for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            distance[b][c] = min(distance[b][c], distance[b][a] + distance[a][c])

# 나라의 개수
count = 0
for i in range(0, n+1):
    if distance[c][i] >= INF:
        distance[c][i] = -1
    else:
        count += 1

# 모든 나라가 메시지를 받는 데 걸리는 시간
for i in range(1, n+1):
    max_value = 0
    array = sorted(distance[i], reverse=True)
    if max_value < array[0]:
        max_value = array[0]

print(count, max_value)