글 읽기 - 파이썬 언어 자체에 대한 질문

4charwon 6년 전 0

다들 푸셨듯이 최소 힙으로 최소 우선순위 큐로 다익스트라 써서 구현했습니다.

파이썬 언어 자체에 대해 의문이 생겨서 질문드립니다.

분명히 뻔히 적혀있는 명령을 이녀석이 구현하질 않네요. 제가 사용중인건 python 3.4입니다.

주석에 여기!라고 적힌 부분을 좀 봐주시기 바랍니다.

---------------------

케이스1

6 6
1
1 2 3
2 3 3
3 4 3
4 6 1
1 5 4
5 4 4

케이스 2

5 6

5 1 1

1 2 2

1 3 3

2 3 4

2 4 5

3 4 6

에러1

Traceback (most recent call last):
File "./prog.py", line 84, in <module>
File "./prog.py", line 63, in decreasekey
TypeError: list indices must be integers, not float

도대체 어떤 부분에서 오류인지 알수가 없습니다. 제가 놓친 것이 무엇인지 아시는 분들, 도움 주시면 정말 감사하겠습니다.

a = input().split()
v = int(a[0])
e = int(a[1])
  
elist = [0] #인접 리스트로 구현하였습니다.
  
for i in range(0,v+1):
    elist.append([])
  
start = int(input())
  
for i in range(0,e):
    a = input().split()
    elist[int(a[0])].append([int(a[1]),int(a[2])])
  
minq = [0] #최소우선순위 큐로 구현했습니다. 각 노드는 key값과 노드 번호를 성분으로 합니다.
adress =[0] #각 노드들이 큐에서 어느 위치에 있는지 저장
qsize = 0
  
def qminheapify(minq,x):
    minimum = x
    global qsize
    global adress
    left = x*2
    right = left+1
      
    if left <= qsize and minq[left][0] < minq[x][0] :
        minimum = left
    if right <= qsize and minq[right][0] < minq[minimum][0] :
        minimum = right
    if x != minimum :
        minq[minimum],minq[x] = minq[x],minq[minimum]
        adress[minq[minimum][1]] = minimum
        adress[minq[x][1]] = x
        qminheapify(minq,minimum)
  
for i in range(1,v+1): #minq를 초기화하고, adress도 초기화
    minq.append([float('inf'),i])
    adress.append(i)
  
qsize = v
      
def extractmin(minq):
    global qsize
    global adress
    print(qsize)
    minq[qsize],minq[1] = minq[1],minq[qsize]

#여기!!! 케이스 2를 입력시 minq의 [0,5]와 [inf,1]이 교체가 일어나질 않습니다. 분명히 적혀있는데!,qsize랑 위치랑 다 맞는데!!
    adress[minq[qsize][1]] = qsize
    adress[minq[1][1]] = 1
    qsize -= 1
    qminheapify(minq,1)
    print(minq)
    return minq[qsize+1]
      
     
  
def decreasekey(minq,x,k):
    global adress
    minq[x][0] = k
    parent = int(x/2)
    while x > 1 :
        if minq[parent][0] <= minq[x][0] :

# 여기!!!!! 케이스 1을 입력시 에러 1이 뜹니다. 분명 바로 위에있는 minq[x][0]에서는 문제가 없거든요!

#minq[x][0]을 minq[int(x)][0]으로 바꾸면 실행이됩니다. 이해할 수 없습니다.

            break
        minq[parent],minq[x] = minq[x],minq[parent]
        adress[minq[parent][1]] = parent
        adress[minq[x][1]] = x
        x = x/2
          
decreasekey(minq,adress[start],0)
 
          
while qsize > 0 :
    ext = extractmin(minq)
    print(minq)
    if ext[0] == float('inf') :
        continue
    ext[0] = int(ext[0])
    vnum = ext[1]
    for i in range(0,len(elist[vnum])):
        u = elist[vnum][i][0]
        w = elist[vnum][i][1]
        if minq[adress[u]][0] > ext[0]+w :
            decreasekey(minq,adress[u],ext[0]+w)
for i in range(1,v+1):
    if minq[adress[i]][0] == float('inf') :
        print("INF")
    else :
        print(minq[adress[i]][0])
 

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

문제

문제

출처

ICPC

파이썬 언어 자체에 대한 질문

4charwon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말