##왕초보

안녕하세요. 아주 평범한 고등학생입니다. 아직 파이썬은 정식으로 배운 적은 없고 학교 생기부 채우느라 구글링하면서 제가 필요한 부분 찾아보면서 조금씩 파이썬 접하고 있습니다. 이번에 다익스트라 알고리즘 구현하려고 구글링해서 그냥 통째로 복사 붙여 넣기하고 아래 인접리스트만 조금 변형했습니다. 하지만 이걸 제가 다 했다고 하기에도 조금…. 이상해서 혹시 다익스트라 알고리즘 구현할 정도의 파이썬 다루는 실력을 만들려면 얼마나 걸리나요?? 저 혼자 코드 짜라고 하면 아무것도 못 할 거 같아서 질문합니다…. import sys def dijkstra(start): # 초기 배열 설정 distances = {node: sys.maxsize for node in graph} # 시작 노드의 거리는 0으로 설정 distances[start] = 0 queue = [] # 시작 노드부터 탐색 시작 하기 위함. (거리, 노드) - 거리, 노드 순으로 넣은 이유는 heapq 모듈에 첫 번째 데이터를 기준으로 정렬을 진행하기 때문 (노드, 거리) 순으로 넣으면 최소 힙이 예상한대로 정렬되지 않음 heapq.heappush(queue, (distances[start], start)) # 우선 순위 큐에 데이터가 하나도 없을 때까지 반복 while queue: # 가장 낮은 거리를 가진 노드와 거리를 추출 current_distance, node = heapq.heappop(queue) # 파이썬 heapq에 (거리, 노드) 순으로 넣다 보니까 동일한 노드라도 큐에 저장이 된다 예시: queue[(7, 'B'), (10, 'B')] # 이러한 문제를 아래 조건문으로 이미 계산되어 저장한 거리와 추출된 거리와 비교하여 저장된 거리가 더 작다면 비교하지 않고 큐의 다음 데이터로 넘어간다. if distances[node] < current_distance: continue # 대상인 노드에서 인접한 노드와 거리를 순회 for adjacency_node, distance in graph[node].items(): # 현재 노드에서 인접한 노드를 지나갈 때까지의 거리를 더함 weighted_distance = current_distance + distance # 배열의 저장된 거리보다 위의 가중치가 더 작으면 해당 노드의 거리 변경 if weighted_distance < distances[adjacency_node]: # 배열에 저장된 거리보다 가중치가 더 작으므로 변경 distances[adjacency_node] = weighted_distance # 다음 인접 거리를 계산 하기 위해 우선 순위 큐에 삽입 (노드가 동일해도 일단 다 저장함) heapq.heappush(queue, (weighted_distance, adjacency_node)) return distances graph = { 'A': {'C': 6.3, 'D': 4, 'E': 7}, 'B': {'C': 3.8, 'F': 7.5, 'K': 15}, 'C': {'A': 6.3, 'B': 3.8, 'D': 6.4, 'F': 4.3, 'K': 14}, 'D': {'A': 4, 'C': 6.4,'E': 5,'F': 4.4}, 'E': {'A': 7,'D': 5,'F': 8.9,'G': 4.5,'H': 8.8}, 'F': {'B': 7.5,'C': 4.3,'D': 4.4,'E': 8.9,'G': 6.5, 'I':5}, 'G': {'E': 4.5,'F': 6.5,'H': 8.5,'J': 6.3}, 'H': {'E': 8.8,'G': 8.5,'J': 7.7}, 'I': {'F': 5,'J': 6.6,'K': 7}, 'J': {'G': 6.3,'H': 7.7,'I': 6.6,'K': 10}, 'K': {'B': 15,'C': 14,'I': 7,'J': 10} } result = dijkstra('A') print(result)