[알고리즘] 탐욕법 - 허프만 알고리즘 코드 (Greedy Approach - Huffman Algorithm Code)

문제)

Description

교재와 강의자료를 참고하여 허프만 코드 트리를 생성하는 허프만 알고리즘의 구현을 완성하시오.

허프만 트리의 리프 노드가 아닌 internal 노드들에는 심볼값으로 '+' 문자를 입력해 두도록 한다.

위 알고리즘을 통해 허프만 트리를 만들었다면, 문자열을 허프만 코드로 인코딩, 디코딩하는 알고리즘을 구현하시오.

허프만 코드 문제에서 preorder, inorder 출력시 마지막에 공백 문자를 출력하지 않도록 하는 것이불필요하게 어렵습니다.

따라서, 이 경우에 한해서만, preorder, inorder 출력시에만 마지막에 공백 문자를 추가해서 출력하시기 바랍니다.

첫 두 줄 preorder, inorder 출력시에만 공백문자 추가할 것. 이후에는 공백 문자 없음.

Input

첫째 줄에 문자의 개수 n이 주어진다.

둘째 줄에 n개의 문자가 주어진다.

문자는 알파벳 대문자, 또는 소문자로만 입력된다고 가정한다.

셋째 줄에 n개의 빈도값이 주어진다.

빈도값은 모두 양의 정수라고 가정한다.

다음 줄에 문자열의 개수 T1이 주어진다.

이후 T1개의 줄에 한 줄에 하나씩 텍스트 문자열이 주어진다.

다음 줄에 문자열의 개수 T2가 주어진다.

이후 T2개의 줄에 한 줄에 하나씩 허프만 코드 문자열이 주어진다.

Output

첫째 줄에 허프만 트리의 preorder traversal 결과를 쓴다. (출력 포맷은 아래 출력 사례를 참조한다.)

둘째 줄에 허프만 트리의 inorder traversal 결과를 쓴다.(출력 포맷은 아래 출력 사례를 참조한다.)

셋째 줄 이후로 T1개의 문자열을 인코딩한 허프만 코드를 한 줄에 하나씩 출력한다.

이후로 T2개의 허프만 코드를 디코딩한 텍스트 문자열을 한 줄에 하나씩 출력한다.

Sample Input 1

6
b e c a d f
5 10 12 16 17 25
5
cab
dec
fad
becadf
fdaceb
5
110001110
011111110
100001
11101111110000110
10010011011111110

Sample Output 1

+:85 +:33 a:16 d:17 +:52 f:25 +:27 c:12 +:15 b:5 e:10 
a:16 +:33 d:17 +:85 f:25 +:52 c:12 +:27 b:5 +:15 e:10 
110001110
011111110
100001
11101111110000110
10010011011111110
cab
dec
fad
becadf
fdaceb

코드)

import heapq

class Node:
    # 노드를 만듬
    def __init__(self, left = None, right = None, symbol = '+', frequency = 0):
        self.left = left
        self.right = right
        self.symbol = symbol
        self.frequency = frequency


def func(pq):
    # 최적 이진 트리를 만드는 함수
    for i in range(n - 1):
        # n개가 있으면 n-1번만 실행한다.
        p = heapq.heappop(pq)
        q = heapq.heappop(pq)       # 빈도수가 작은 두 개의 노드를 꺼냄

        node = Node(p[1], q[1], frequency = p[0] + q[0])        # 새로운 노드를 만듬

        heapq.heappush(pq, [node.frequency, node])      # 새로운 노드를 pq에 넣음

    return heapq.heappop(pq)[1]     # 마지막에 남아 있는 root 노드를 반환함


def preorder(node):
    # preorder 함수
    if node:
        print(f'{node.symbol}:{node.frequency} ', end='')
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    # inorder 함수
    if node:
        inorder(node.left)
        print(f'{node.symbol}:{node.frequency} ', end='')
        inorder(node.right)


def incoding():
    # 문자를 이진 코드로 나타냄
    case = int(input())
    for i in range(case):
        print(''.join(map(lambda x: code[x], input())))     # input 받은 string을 코드화 시킴


def decoding():
    # 이진 코드를 문자열로 변경함
    case = int(input())
    for _ in range(case):
        code = list(input())

        node = r        # 하나의 문자를 출력하면 루트로 돌아가야함

        for c in code:      # 문자 하나씩 꺼내서
            if c == '0':        # 0이면 왼쪽
                node = node.left
            elif c == '1':      # 1이면 오른쪽
                node = node.right

            if node.left == None and node.right == None:
                # 더 이상 갈 곳이 없다면 최하단 노드이므로 출력
                print(node.symbol, end='')
                node = r        # 출력 후 다시 루트로 돌아감
        print()


def create_default_priority_queue():
    # pq를 생성함
    pq = []
    for i in range(n):
        # 문자와 빈도수로 pq를 만듬
        node = Node(None, None, chs[i], ch_freq[i])     # 노드를 생성함
        heapq.heappush(pq, [node.frequency, node])      # 생성 후 pq에 집어 넣음
    return pq


def find_code(temp, ch, node):
    # 문자에 해당하는 이진 코드를 찾는 함수
    if node:
        if ch == node.symbol:
            # 만약 ch와 symbol이 맞다면 True를 return함
            return True
        else:
            temp.append('0')        # 0을 먼저 집어 넣고
            if find_code(temp, ch, node.left):
                # True라면 문자에 해당하는 이진 코드를 찾았으므로 True를 return 함
                return True
            temp.pop()      # False라면 0을 뺌

            temp.append('1')
            if find_code(temp, ch, node.right):
                return True
            temp.pop()


def create_code():
    # 문자에 맞는 이진 코드를 생성하는 함수
    c = dict()      # 딕셔너리 형태로 넣을거임
    temp = list()       # 임시적으로 코드를 저장하는 곳
    for i in chs:
        find_code(temp, i, r)       # 코드를 찾음
        c[i] = ''.join(temp)        # 딕셔너리에 저장함
        temp.clear()
    return c


if __name__ == "__main__":
    n = int(input())
    chs = input().split()  # 문자를 입력 받음
    ch_freq = list(map(int, input().split()))  # 문자의 빈도수를 입력받음

    pq = create_default_priority_queue()        # 우선순위 큐를 만듬
    r = func(pq)        # 우선순위 큐를 가지고 최적 이진 코드 트리를 만들고, root를 반환 받음

    for order in [preorder, inorder]:
        # preorder, inorder 출력
        order(r)
        print()

    code = create_code()      # 알파벳에 맞는 코드를 찾음
    incoding()      # 알파벳에 맞게 이진 코드를 출력함
    decoding()      # 이진 코드에 맞게 알파벳을 출력함

 

 

주의점)

입력되는 이진 코드가 정확한 이진 코드가 아닐 수도 있다.

마지막에 0이 남을 수도 있음 -> 재귀가 아닌 반복문으로 해결

heapq에서 빈도수 기준으로 노드를 정렬하려면 리스트 형태로 넣으면 된다.

리스트의 앞 부분을 기준으로 정렬함

 

2번째 코드)

from collections import deque
import heapq


class Node:
    # 노드 클래스를 만듬
    def __init__(self, left=None, right=None, symbol='+', frequency=0):
        self.left = left
        self.right = right
        self.symbol = symbol
        self.f = frequency


def func(pq):
    # 허프만 트리를 만듬

    for _ in range(n - 1):
        # n개의 원소이므로 n - 1번 반복해야함

        p = heapq.heappop(pq)[1]
        q = heapq.heappop(pq)[1]
        # 작은거 두 개 꺼냄

        r = Node(left=p, right=q, frequency=p.f + q.f)      # 새로운 노드 생성
        heapq.heappush(pq, (r.f, r))        # r을 넣음

    return heapq.heappop(pq)[1]


def preorder(node):
    if node != None:
        print(f'{node.symbol}:{node.f} ', end='')
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node != None:
        inorder(node.left)
        print(f'{node.symbol}:{node.f} ', end='')
        inorder(node.right)


def encoding(r, ch, encode):
    # 문자열을 인코딩하는 함수
    if r.symbol == '+':
        # 연결 노드라면 우선 다 탐색해봐야함
        encode.append(0)
        encoding(r.left, ch, encode)
        encode.pop()

        encode.append(1)
        encoding(r.right, ch, encode)
        encode.pop()

    elif r.symbol == ch:
        # 만약 심볼이 ch와 같다면
        global real
        real += ''.join(map(str, encode))

        return


def decoding(r, code):
    node = r        # node를 최상단 노드로 초기화
    for c in code:      # 앞에서 순차적으로
        if c == 0:
            node = node.left
        else:
            node = node.right

        if node.left == None and node.right == None:
            # 둘 다 None이면 잎에 도달한 것임, or은 안 됨
            print(node.symbol, end='')
            node = r


n = int(input())        # 문자의 개수
chs = input().split()       # 문자
freq = list(map(int, input().split()))      # 빈도수

pq = []

for i in range(n):
    # node들을 빈도수 기준으로 pq에 넣음
    node = Node(symbol = chs[i], frequency = freq[i])
    heapq.heappush(pq, (node.f, node))

r = func(pq)        # 최상단 노드를 얻어옴

# 아래는 출력
preorder(r)
print()
inorder(r)
print()


T1 = int(input())       # 문자열의 개수
for _ in range(T1):
    # 문자를 코드화
    real = ''       # 진짜 이진코드
    for ch in input().strip():
        encode = []     # 일시적인 이진코드
        encoding(r, ch, encode)
    print(real)

T2 = int(input())       # 이진코드
for _ in range(T2):
    # 코드를 문자화
    code = list(map(int, input().strip()))
    decoding(r, code)
    print()