알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 9. 최단 경로 - 전보

  • 0
  • 0
0
0

1. 전보

  • 난이도
  • 풀이 시간
    • 60분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB
  • 기출
    • 유명 알고리즘 대회

A. 문제

여러 나라에 N개의 도시가 있다.
각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 메시지를 전송할 수 있다.
X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다.
통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.

어느날 C라는 도시에서 위급 상황이 발생했다.
그래서 최대한 많은 도시로 메시지를 보내고자 한다.
메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나간다.
각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 떄, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하라.

a. 입력 조건
  • 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C
    • 1 <= N <= 30,000
    • 1 <= M <= 200,000
    • 1 <= C <= N
  • M+1번째 줄까지 통로에 대한 정보 X, Y, Z가 주어진다.
    • 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메시지가 전달되는 시간은 Z이다.
    • 1 <= X, Y <= N
    • 1 <= Z <= 1,000
b. 출력 조건
  • 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다
c. 테스트 케이스
  • 입력 예시

    
    3 2 1
    1 2 4
    1 3 2
    
    
  • 출력 예시

    
    2 4
    
    

B. 내 답안


# n개의 도시가 있다.  
# 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다.  
# X -> Y로 전보를 보내려면 X에서 Y로 향하는 통로가 설치되어 있어야 한다. => 단방향  
  
# C라는 도시에서 메시지를 보내려고 한다.  
# 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나간다.  
# 각 도시의 번호와 통로 정보가 주어졌을때,  
# 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇개  
# 모두 메시지를 받는데 걸리는 시간을 얼마인가  
  
# Input  
 # n, m, c = 도시의 개수, 통로의 개수, 메시지를 보내고자 하는 도시  
 # M+1줄까지 통로에 대한 정보 x,y,z # 특정 도시 x에서 y로 이어지는 통로가 있고, 전달 시간이 z임.  
  
# Output  
 # 첫째줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 걸리는 시간.  
  
import heapq  
  
INF = int(1e9)  
  
n, m, c = list(map(int, input().split()))  
  
graph = [[] for _ in range(n+1)]  
distance = [INF] * (n+1)  
# distance[c] = 0  
  
  
for i in range(m):  
    a, b, z = list(map(int, input().split()))  
  
    graph[a].append((b, z))  
  
# print(*graph, sep='\n')  
  
def dijkstra(start):  
    q = []  
    # print(start)  
    # print(graph[start]) heapq.heappush(q, (0, start))  
    distance[start] = 0  
    # distance[0] = 0  
    count = 0  
    while q:  
        c, b = heapq.heappop(q)  
  
        if distance[b] < c:  
            continue  
  
    for i in graph[b]:  
            cost = c + i[1]  
            if cost < distance[i[0]]:  
                distance[i[0]] = cost  
                heapq.heappush(q, (cost, i[0]))  
                count = count + 1  
 # if i[1] < distance[b]:  
 #     distance[b] = i[1] #     count = count + 1 #     heapq.heappush(b, distance[b]) return count  
  
count = dijkstra(c)  
print(distance)  
print(count, end=' ')  
print(max(distance))

a. 회고

풀이

A에서 B로 가는 최단 경로 -> 다익스트라 알고리즘이 바로 떠올랐다.

반성

다익스트라 코드 구현을 완성하지 못했다.

결론

잘 구현될때까지 반복해서 복습해야겠다.

C. 문제 해설

한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있으므로 다익스트라 알고리즘으로 해결할 수 있다.
N, M의 범위가 충분히 크기 때문에, 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성해야 한다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #최단경로 #다익스트라 #전보

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.