08. 고급 탐색 알고리즘 - 핵심 유형 문제풀이 - 힙, 자료구조

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

ref:

https://velog.io/@jsbryan/%ED%9E%99-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%B5%9C%EB%8C%80-%ED%9E%99

힙 (최소 힙, 최대 힙)

 

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

• 힙, 자료구조, 그리디

from collections import deque
import heapq, sys 

n = int(sys.stdin.readline().strip())

data, count = [], 0

for _ in range(n):
    x = int(sys.stdin.readline().strip())
    heapq.heappush(data, x)



while len(data) !=1 :
    x = heapq.heappop(data)
    y = heapq.heappop(data)
    sum_value = x+y
    count += sum_value
    heapq.heappush(data, sum_value)

print(count)

생각해보면 정말 간단한 문제였음

• 최소힙 기준으로 입력을 받고 하나씩 꺼낸다는게 생각의 문제였음
• 힙을 빼낼 때 2개씩 빼내고 2개의 sum 값을 다시 넣어주면됨.

https://www.acmicpc.net/problem/1766

1766번: 문제집

• 힙, 위상정렬

 

• 진입차수(시작노드): 자기자신으로 오는 간선(1, 6) 즉 자기 자신으로 들어오는 간선이 없는 것들
  • 1,6을 큐에 넣고 이후 1, 6을 큐에서 꺼내 간선을 제거 하여 2,4를 다시 큐에 넣음
• 사이클이 존재한다는 의미는 예를 들어 3 -> 1 로 돌아가게 되면 3보다 1이 먼저 풀려야 하는데 1보다 3이 먼저 풀려야 한다는 뜻임 즉 사이클이 존재하면 "위상정렬"이 아니다.

 

• "힙"을 "우선순위 큐"라고도 함.

import sys, heapq

n, m = map(int, sys.stdin.readline().split())
# n+1한 이유는 그냥 for문이 0부터 시작하니까 계산을 용이하게 하려고 n+1 한듯
array = [[] for _ in range(n+1)] # 모든 노드에 대해서 자기가 어떤노드에 연결되어있는지
indegree = [0] * (n+1) # 현재 간선이 이어진 진입차수가 몇인지 확인하기 위해

heap = []
result = []

# 노드 연결 확인
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    array[x].append(y) # x랑 y연결
    indegree[y] += 1 #진입 차수를 확인 하기 위해 
# print(array, indegree)

# 알고리즘 설명처럼 진입차수가 0인 것을 정점을 큐에 삽입
for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i) # 큐 삽입
# print(heap)

result = []

while heap: # 여기선 heap = queue 알고리즘의 2와 3을 반복하는 내용
    data = heapq.heappop(heap) # 큐에서 데이터를 하나씩 꺼냄 ---3 
    result.append(data)
    for y in array[data]: # --- 1
        indegree[y] -= 1 # ----1 로된 간선 제거
        if indegree[y] == 0: # 0이 되었으면
            heapq.heappush(heap, y) # 힙에다가 다시 y값 삽입

for i in result:
    print(i, end=' ')

• 알고리즘 구현 순서
  1. n,m 입력 및 간선 연결여부 확인용 array와 진입차수 체크를 위한 indegree 생성
  2. x,y 간선간 연결 확인 입력 받은 후 간선 array에 대입(array[x].append(y)) 및 진입차수 체크를 위한 indegree[y] +=1
  3. heap과 같은 우선순위 큐 생성. ->진입차수 0인 값부터 시작하기 위함. 
     1. for _ in range(1, n+1): if indegree[i] == 0: heapq.heappush(heap, i)
  4. 결과 값을 위한 result 변수 생성 및 while 위상정렬 수행 -> 진입차수가 0부터인 heap으로 시작됨
     1. 기존 heap에서 추출 - > data = heapq.heappush(heap) -> 결과값 어팬드 -> result.append(data)
     2. 연결된 간선 확인 -> for y in array[data] ->  진입차수 1 낮추기 -> indegree[y] -= 1
     3. 만약 진입차수가 0 이면 다시 heap에 추가 - > if indegree[y] ==0: heapq.heappush(data, y)

 

# 위상자료
import sys, heapq

n, m = map(int,sys.stdin.readline().split())
array = [[] for _ in range(n+1)] # 간선확인
check = [0] * (n+1) # 진입 차수 확인

for _ in range(m):
    x, y = map(int,sys.stdin.readline().split())
    array[x].append(y)
    check[y] += 1

# print(array, check) 

heap = [] # 스택 생성 -> 우선순위 큐
for i in range(1, n+1): # 진입차수를 판단하기 위해 -> 진입차수가 0인 것부터 비교
    if check[i] == 0:
        heapq.heappush(heap, i)

# print(array, check, heap) 
        
result = [] # 결과 값

while heap:
    x = heapq.heappop(heap) #  0 진입차수 처음부터 뽑기
    result.append(x) # 뽑은 결과 값 추가
    for y in array[x]: # 뽑혔던 집입차수 간선 확인
        check[y] -= 1 # 간선 제거
        if check[y] == 0: # 0이 되면
            heapq.heappush(heap, y) # 다시 연결되었던 힙에 추가

# 뽑고 -> 결과 추가하고 -> 뽑현던거 간선 확인 -> 간선 제거 ->간선 연결된게 남아있으면 반복.
for j in result:
    print(j, end=" ")