글 읽기 - 1753) Python3로 작성하였는데 답이 틀리다고 나와 도움을 요청드립니다

jsy8481 4년 전 0

예제와 5%까지는 평가가 되고 그 후 답이 틀렸습니다. ( 문제점을 찾는데 참고가 될까 올립니다.)

최소힙을 이용한 다익스트라 알고리즘을 만들고 싶었습니다.

최소 힙을 위한 insert_heap() 함수와 delete_heap() 함수를 만들었고

heap에는 간선의 도착지와 거리(노드까지의 거리 + weight)가 추가되고 삭제됩니다.

어디서 잘못되어 문제가 되는지 찾고 있으나 발견을 못하여, 도움을 요청드립니다.

감사합니다!

import sys
# sys.stdin = open('sample_input.txt','r')
def input():
    return sys.stdin.readline()

# V - 노드 E - 간선
V,E = list(map(int,input().strip().split()))
start = int(input().strip())

#dictionary로 간선 구성
# 노드의 번호는 1부터 시작(i+1), 튜플로 딕셔너리의 키와 값을 표현하고
# 이들의 리스트를 이용하여 딕셔너리 생성
graph = dict([(i+1,[]) for i in range(V)])

# Edge의 수 만큼 입력을 받음
for _ in range(E):
    edge = list(map(int,input().strip().split()))
    # edge가 2개 일수도 있음!
    graph[edge[0]].append((edge[1],edge[2]))
    
# 키 - 시작 노드, 값 튜플(도착점,가중치) 리스트

# 사용할 데이터 구조인 최소 힙 생성 / 삽입과 삭제 연산을 만들어야 한다.
heap = []

# 삽입 연산
def insert_heap(edge):
    heap.append(edge)
    index = len(heap)-1
    while True:
        # 루트 노드까지 도달했다면 정지
        if index == 0:
            break
        # 부모의 값이 더 크다면 교체하고 부모로 인덱스를 변경
        if heap[index//2][1] > heap[index][1]:
            heap[index//2],heap[index] = heap[index],heap[index//2]
            index = index//2
        # 부모의 값이 크거나 같으면 정지한다.
        else:
            break

# 삭제 연산
def delete_heap():
    heap[0],heap[-1] = heap[-1],heap[0]
    return_v = heap.pop(-1)
    return_v = return_v
    index = 0
    while True:
        left = 2*(index+1)-1
        right= 2*(index+1)
        if left > len(heap)-1:
            break
        elif left == len(heap)-1:
            if heap[index][1] > heap[left][1]:
                heap[index],heap[left] = heap[left],heap[index]
            
            break
            
        else:
            use_v = 'v'
            if heap[left][1] < heap[right][1]:
                use_v = left
            else:
                use_v = right
            if heap[index][1] > heap[use_v][1]:
                heap[index],heap[use_v] = heap[use_v],heap[index]
                index = use_v
            else:
                break
    return return_v

visit = [0 for _ in range(V+1)]
distance = [-1 for _ in range(V+1)]
cost = 0
insert_heap((start,0))

while True:
    if len(heap) == 0:
        break
    node = delete_heap()
    index, d = node
    if visit[index] == 1:
        continue
    distance[index] = d
    visit[index] = 1
    for edge in graph[index]:
        v = edge[0]
        if visit[v] == 0:
            insert_heap((v,edge[1]+d))
    
for i in range(V):
    if distance[i+1] == -1:
        print('INF')
    else:
        print(distance[i+1])

sait2000 4년 전 1

insert_heap에서 부모 인덱스가 틀리지 않나요? 그리고 참고로 heapq 모듈로 힙 구현이 있어요.

jsy8481 4년 전 0

heapq 모듈이 있군요 참고해보겠습니닷

index//2로 하면 부모로 가지 않나요??

jsy8481 4년 전 0

(index-1)//2를 해야했네용!! 수정해서 해볼게요 감사합니닷

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1753) Python3로 작성하였는데 답이 틀리다고 나와 도움을 요청드립니다

jsy8481 4년 전 0

sait2000 4년 전 1

jsy8481 4년 전 0

jsy8481 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말