[내일배움캠프 4-3일] 스쿼드 과제, heapq, 인접 리스트, BFS

최소 힙

우선 파이썬의 heapq 모듈을 먼저 공부했음.

링크 : https://littlefoxdiary.tistory.com/3

우선 최소 힙의 구조는 이러한 모습.

부모 노드의 키값이 자식 노드보다 항상 작다. 즉 루트가 항상 가장 작은 값이 되는 구조.

 

파이썬에서는 heapq 알고리즘을 제공한다.

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop 하고 리턴, 비어있다면 IndexError 호출
• heapq.heapify(arr) : 리스트 arr 를 즉각적으로 heap으로 변환

이중 heappush와 heappop을 활용해서 문제를 해결하였음.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
# 빈 리스트 heap 생성, heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하는 역할
heap = []

for _ in range(N):
    x = int(input())
    # 입력값 0일 때
    if x == 0:
        # heap에 아무것도 없다면 0 출력
        if len(heap) == 0:
            print(0)
        # 아니라면 최소값 출력
        else:
            print(heapq.heappop(heap))
    # 입력값 자연수일때
    else:
        heapq.heappush(heap, x)

---

문제점

heapq 모듈은 최소 힙으로 구현되어 있음. 즉 최대 힙을 제공하지 않는다.
최대 힙 문제가 나온다면 어떻게 해결할지?

 

해결방안

사실 간단함.

부호를 바꿔서 최대값이 최소값이 되도록 해주면 됨.

이때 데이터 보존을 위해 튜플 형태로 값을 저장해주고, 인덱싱을 통해 문제에 따라 접근하면 된다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

예시 코드

[(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)] 이런 식으로 저장된다.

---

트리의 부모 찾기

우선 인접 리스트를 이해한다.

import sys

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

# 그래프 초기화
graph = [[] for i in range(n+1)]

# 연결된 두 정점 입력
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

graph를 초기화 할 때 범위를 n+1까지 선언

정점 번호는 1번부터 시작하기 때문에 graph의 0번 인덱스는 안쓰는 칸이 된다. 즉 8개의 칸이 필요한 것

graph 초기화 직후.

graph에 정점을 입력 후 출력.

이해를 쉽게 하기 위해 출력해봤음.

강의에서는 딕셔너리 구조였던 것으로 기억한다.

# 부모 노드를 저장할 리스트 생성
parents = [0] * (n + 1)

# BFS를 위한 큐 초기화
queue = deque([1])
# 루트 노드의 부모는 없음, -1을 입력해 놓는 것
parents[1] = -1

부모 노드를 저장할 리스트를 만들어 최종적으로 출력하면 됨.

queue를 만드는데 1은 루트 노드이므로 초기화 하면서 넣어놓는 것.
parents 리스트에는 부모 노드가 저장되어야 함. 1은 부모 노드가 없으므로 -1을 할당해 주는 것.

# BFS 수행
while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        # 아직 방문하지 않은 노드라면 부모 노드 입력 후 queue에 추가
        if parents[neighbor] == 0:
            parents[neighbor] = current
            queue.append(neighbor)

이 부분이 가장 헷갈린 부분.
그림판으로 직접 그리면서 천천히 진행했다.

queue에 아무것도 없을 때까지 루프.

queue에서 popleft를 하여 current 변수에 저장. 시작은 1

graph[1] = [6, 4] 즉 노드 1과 인접한 수 6과 4가 할당되어 있으므로 neighbor라는 변수를 사용하여 for문으로 하나씩 대입.

만약 parents[6] == 0 이라면 이걸 현재 current 값인 1로 바꿔준다. 6의 부모에 1이 저장되는 것. 이후 queue에 6 저장.

다음에는 parents[4] == 0 이기 때문에 역시 current인 1로 바꿔주고 1의 부모에도 1을 저장. 역시 queue에 1 저장.

이런 식으로 반복하면서 이미 parents에 어떤 값이 할당되었다면 스킵하면서 parents 리스트를 채워준다.

queue에 아무것도 남지 않으면 탈출.

자신과 인접한 모든 노드를 우선으로 탐색하는 너비우선 탐색 방법

# 2번 노드부터 차례대로 부모 노드 출력
for i in range(2, n + 1):
    print(parents[i])

parents 리스트를 2번 노드부터 출력해주면 끝.

 

# 트리의 부모 찾기
# 인접 리스트 활용

import sys
from collections import deque

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

# 그래프 초기화
graph = [[] for i in range(n+1)]

# 연결된 두 정점 입력
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# 부모 노드를 저장할 리스트 생성
parents = [0] * (n + 1)

# BFS를 위한 큐 초기화
queue = deque([1])
# 루트 노드의 부모는 없음, -1을 입력해 놓는 것
parents[1] = -1

# BFS 수행
while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        # 아직 방문하지 않은 노드라면 부모 노드 입력 후 queue에 추가
        if parents[neighbor] == 0:
            parents[neighbor] = current
            queue.append(neighbor)

# 2번 노드부터 차례대로 부모 노드 출력
for i in range(2, n + 1):
    print(parents[i])

최종 코드.

---

오늘의 회고

수요일이라 그런지 집중력이 조금 떨어졌다.

그래도 목표로 한 1주차 힙 삽입&추출, 연결 리스트 복습 + 스쿼드 과제 세개 마무리.

 

내일의 목표는 스쿼드 과제 완료 + 2주차 진도 좀 나가보자 제발