글 읽기 - 파이썬 heapq 오류를 발견한거 같습니다

whdgurclzls 4년 전 0

########코드보다 왜 heapq를 사용하는데 큰 값이 작은 값보다 먼저 위치하게 되었나가 주된 내용입니다.

b라는 배열에 heapq를 사용한 코드인데, 디버깅 중에 heapq를 출력해보니 더 큰값이 더 작은값보다 앞에 위치하는걸 발견했습니다.

코드는 아래와 같고

#입력 예제는 이렇습니다.

'''
1
2 2 10
1 1
0 2

'''

코드 돌려봤을때 두번째줄 결과가

[[0, 1, 0, 0], [1, 2, 1, 1], [0, 1, 0, 1]] 입니다. 분명 b배열은 heappush만으로 처리 했는데 대체 왜 어떻게... 더 큰 [1, 2, 1, 1] 값이 [0, 1, 0, 1] 값보다 먼저 나오게 되었을까요???

배열 크기를 제가 잘못생각하나 해서 파이썬에 sorted([[0, 1, 0, 0], [1, 2, 1, 1], [0, 1, 0, 1]]) 출력해봤더니 [[0, 1, 0, 0], [0, 1, 0, 1], [1, 2, 1, 1]] 이렇게 나와서 그 문제 같진 않네요..

from collections import*
from heapq import*
dd=[(-1,0),(0,1),(1,0),(0,-1)]
for tc in range(int(input())):
    n, m, k = map(int,input().split())
    a=[];b=[];c=[]
    check={}
    for i in range(n):
        a.append(list(map(int,input().split())))
        for j in range(m):
            if a[i][j]:
                heappush(b, [a[i][j], a[i][j], i, j])
                check[(i, j)]=1
    for _ in range(k):
        print(_, b)
        active={}; active_list=[]
        for i in range(len(b)): #시간 1씩 사용
            b[i][0]-=1
        while b:                #비활성 처리
            t, v, x, y = heappop(b)
            if t < 0:
                heappush(c, [v, v, x, y])
                for dx, dy in dd:
                    nx ,ny = x+dx, y+dy
                    try:
                        if check[(nx, ny)]: continue
                    except:pass
                    try:
                        if active[(nx, ny)]:    #있으면 비교해서 큰거
                            active[(nx, ny)] = max(v, active.get((nx, ny)))
                    except:                     #없으면
                        active[(nx, ny)] = v
                        active_list.append((nx, ny))
            else:
                heappush(b, [t, v, x, y])
                break
        for x, y in active_list:    #번식된거 마무리
            v = active.get((x, y))
            heappush(b, [v, v, x, y])
            check[(x, y)]=1
        for i in range(len(c)): #활성 처리
            c[i][0]-=1
        while c:
            t, v, x, y = heappop(c)
            if t >= 0:
                heappush(c,[t, v, x, y])
                break
    print('#{} {}'.format(tc+1, len(b)+len(c)))

djm03178 4년 전 2

힙은 부모가 두 자식들보다 크지 않은 것을 보장하는 것이지, 자식들간의 대소는 보장하지 않습니다. 원소가 3개 들은 경우 0번째 원소는 1번째와 2번째 원소의 부모이므로 이 둘보다 크지 않음이 보장되고, 1번째와 2번째 원소 사이의 대소 관계는 보장되지 않습니다.

djm03178 4년 전 2

또한 힙은 그러한 성질을 이용해서 전체에서 가장 작은 원소를 빠르게 찾는 것이 목적인 것이고 전체가 정렬되는 것과는 무관한 자료구조입니다. sorted와는 전혀 성질이 다릅니다.

whdgurclzls 4년 전 1

그렇군요!! 정렬 상태를 유지해 주는 건줄 알았네요..

덕분에 배워갑니다!

너무 궁금해서 어그로성 제목 달았는데도 친절한 답변 주셔서 감사합니다! 복받으세요~~

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

문제

문제

출처

ICPC

파이썬 heapq 오류를 발견한거 같습니다

whdgurclzls 4년 전 0

djm03178 4년 전 2

djm03178 4년 전 2

whdgurclzls 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말