파이썬으로 이해하는 트리,그래프

정글에서는 목요일이 한주의 끝이자 시작이다.

 

여러가지 자료구조와 알고리즘을 다루는 2주차가 마무리되고, 3주차 과제가 등장했다.

바로 코딩테스트에 단골로 등장하는 그래프이다.

 

키워드가 워낙 많아서 뭐부터 공부할지 고민하다 일단 트리의 순회부터 보기로 했다.

 

Tree

- 1개 이상의 유한한 개수의 노드의 집합

- 루트 노드와 0개 이상의 겹치지 않는 하위 나무 구조들의 집합으로 이루어짐

 

트리와 관련된 여러 용어가 있지만 일단은 넘어가겠다

(파이썬으로 트리를 어떻게 다루는지가 주제니깐)

다만 나중에 나올 최소신장트리를 이해하기 위해서도 잘 알아둘 필요는 있다!

 

트리 순회

흔히 전위,중위,후위 순회를 자주 다룬다.

 

전위:  루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회

중위:  왼쪽 서브트리 - 루트 -오른쪽 서브트리 순으로 순회

후위:  왼쪽 서브트리 - 오른쪽 서브트리- 루트 순으로 순회

 

트리는 C에서 아마 구조체였나..? 로 다뤘던 거 같은데

파이썬에선 클래스로 구현하는 방법이 있었다.

 

class TreeNode:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None

 

자바에 익숙한 나에겐 희소식이었다. 희희

 

다음으로 재귀를 이용한 순회 방법을 보자. 위에서부터 전위,후위,중위 순회이다.

def preorder(node):
    if node==None:
        return
    
    print(node.val, end='')
    preorder(node.left)
    preorder(node.right)

def postorder(node):
    if node==None:
        return
    
    postorder(node.left)
    postorder(node.right)
    print(node.val, end='')

def inorder(node):
    if node==None:
        return
    
    inorder(node.left)
    print(node.val, end='')
    inorder(node.right)

 

분할정복을 왜 2주차에 했는지 알 수 있는 부분이었다.

 

 

 

이진검색트리(백준 5639번)

필수적으로 알아야 할 개념

1. 클래스, 필드 설정
2. 전위,중위,후위 순회 방법
3. 전위로 순회한 원소 리스트를 후위로 바꾸는 방법

 

import sys
sys.setrecursionlimit(10 ** 6)
node = [int(readline.rstrip()) for readline in sys.stdin]

def postorder(root_idx,end_idx):
    if root_idx > end_idx:
        return
    
    root=node[root_idx]
    start_idx=root_idx+1

    while start_idx<=end_idx:
        if root< node[start_idx]:
            break
        start_idx+=1

    
    postorder(root_idx+1, start_idx-1)
    postorder(start_idx, end_idx)
    print(root)

postorder(0,len(node)-1)

 

문제 자체가 전위로 순회한 원소리스트를 후위로 바꾸는 문제였다.

EOF 때문에 시간이 오래 걸리기도 했다..

 

전위로 순회한 원소가 리스트에 쭉 있을 때

결국 루트 - 왼쪽 서브 트리 - 오른쪽 서브 트리로 구성되어 있으므로

우리는 어디가 새로운 트리의 시작점인지를 찾아야 하는데, 그 기준이 되는 것이 바로 

이진 검색 트리의 특성이다.

 

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

 

따라서 루트 값이 있고 일정 범위동안 루트보다 작은 값이 이어지다가, 어느 순간 값이 확 튀는(루트 이상의) 지점이 생길 것이고

(그 지점이 없다면 오른쪽 서브 트리가 없는 거겠지?)

우리는 그 인덱스를 오른쪽 서브트리의 시작지점으로 잡고 재귀를 통해 연산을 이어 나갈 수 있다.

 

+ 수정

저렇게 오른쪽 서브 트리를 선형탐색으로 찾으면 시간이 많이 드니, 이진탐색으로 빠르게 찾자!

import sys
sys.setrecursionlimit(10**6)
node = [int(line.strip()) for line in sys.stdin]

def postorder_optimized(root_idx, end_idx):
    if root_idx > end_idx:
        return
    
    root = node[root_idx]
    
    # 이진 탐색으로 분할점 찾기
    left = root_idx + 1
    right = end_idx + 1
    
    # root보다 큰 첫 번째 원소의 인덱스 찾기
    while left < right:
        mid = (left + right) // 2
        if node[mid] > root:
            right = mid
        else:
            left = mid + 1
    
    split_idx = left
    
    # 재귀 호출
    postorder_optimized(root_idx + 1, split_idx - 1)  # 왼쪽 서브트리
    postorder_optimized(split_idx, end_idx)           # 오른쪽 서브트리
    print(root)

postorder_optimized(0, len(node) - 1)

 

import sys
sys.setrecursionlimit(10**6)
input_lines = [int(line.strip()) for line in sys.stdin]


class TreeNode:
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None


def build_Tree(preorder):
    if not preorder:
        return None
    
    def build(min_val, max_val):
        nonlocal idx
        if idx>=len(preorder):
            return None

        val= preorder[idx]
        if val<min_val or val> max_val:
            return None
        
        idx+=1
        root= TreeNode(val)
        root.left=build(min_val,val)
        root.right=build(val,max_val)
        return root
    
    idx=0
    return build(float('-inf'),float('inf'))

def postorder(root):
    if root:
        postorder(root.left)          
        postorder(root.right)
        print(root.val)

root= build_Tree(input_lines)
print(root)

 

혹은 이렇게 클래스를 이용해 직접 트리를 만들고 후위 순회를 하는 것이 훨씬 빠르다.(이진탐색때와 거의 같음)

 

---

여기까지가 트리의 내용이고, 다음으로는 그래프를 보자.

마찬가지로 그래프의 정의와 관련 개념설명은 일단 생략하겠다.

 

최소 스패닝 트리

스패닝 트리는 사이클이 없는, 모든 정점을 이은(V-1개의 간선) 트리이고,

최소는 그 가중치의 합이 최소가 되도록 하는 트리이다.

 

파이썬은 이 그래프 구성을 [] 을 써서 표현한다

graph= [ [] for _ in range(n)] # n개 정점
graph[0].append((weight, node))  # (가중치, 정점) 튜플로 저장

 

이 MST를 구하는 알고리즘은 크게 두가지이다.

 

크루스칼 - 간선 중심

모든 간선을 가중치 순으로 정렬하고

가장 가중치가 작은 간선부터 선택하며

사이클이 생기면 제외, 안생기면 추가

V-1개 간선이 선택될 때까지 반복

 

하는게 과정인데, 문제는 저 사이클이다.

 

구현에 유니온-파인드가 들어간다.

유니온 파인드 개념도 일단은 생략한다.

 

우선 구현 코드를 보자

import sys
input= sys.stdin.readline
import heapq as hq

V,E= map(int,input().split())

# 크루스칼에서 사용할 리스트
edges=[]

for _ in range(E):
    a,b,c=map(int,input().split())
    edges.append((a,b,c))

# cost가 적은것부터 정렬
edges.sort(key=lambda x: x[2])

# 유니온 파인드
parent= [i for i in range(V+1)]

def find(x):
    if(parent[x]==x):
        return x
    parent[x]=find(parent[x])
    return parent[x]

def union(a,b):
    pa,pb= find(a),find(b)  
    if pa<pb:
        parent[pb]=pa
    else:
        parent[pa]=pb

answer=0

for a,b,cost in edges:
    if find(a)!=find(b):
        union(a,b)
        answer+=cost

print(answer)

사실 저 find와 union 함수는 템플릿처럼 외워서 쓰다보니,

그안의 로직까지 기억이 잘 안나기도 한다.

다익스트라랑 BFS/DFS도 마찬가지지 뭐..

 

다음 포스팅에선 핵심 로직을 다뤄보기로!

 

 

프림 - 정점 중심

과정

임의 정점에서 시작

현재 트리에서 가장 가까운 정점 추가

모든 정점을 포함할때까지 반복

 

구현은 우선순위 큐를 사용한다.

import sys
input= sys.stdin.readline
import heapq as hq

V,E= map(int,input().split())

# graph= [ [] *(V+1)]
graph = [[] for _ in range(V + 1)]

for _ in range(E):
    a,b,c= map(int,input().split())
    graph[a].append((c,b))
    graph[b].append((c,a))

pq=[(0,1)]
visited= [False]* (V+1)
total_cost=0

while pq:
    weight, node= hq.heappop(pq)

    if visited[node]:
        continue

    visited[node]=True
    total_cost+=weight

    for  next_cost, next_node in graph[node]:
        if not visited[next_node]:
            hq.heappush(pq,(next_cost,next_node))

print(total_cost)

 

방문 처리와 우선순위 큐가 인상적이다.

 

 

두 방법 모두 클래스보단 튜플이 사용하기 편한것 같아 튜플을 선택했다.

 

간혹 크루스칼과 프림의 동작과정을 헷갈릴 수 있는데,

크루스칼은 집합이 여럿 생성되고 마지막에 연결되는 느낌이라면

프림은 하나에서 시작해 다른 정점을 정복해가는 느낌이라 보면 된다.

 

 

또한 두 방법 모두 정렬과 우선순위 큐를 사용하기 때문에, 현재 선택한 정점이 최적의 해라는

그리디의 개념이 포함되어 있다.(다익스트라도 마찬가지다)

그리디는 다음주에 나올 내용이지만, 그래프 탐색에서 너무 많이 등장하므로 이정도는 알아두자!

 

 

---

다익스트라

 

다익스트라 문제는 자바에서 항상 클래스를 통해 풀었는데,

class Edge: 
	def __init__(self, to, weight): # 생성자 
		self.to = to 
		self.weight = weight

graph = [[] for _ in range(3)] 
graph[0].append(Edge(0, 0)) # "Edge 생성: to=0, weight=0" 출력됨

 

파이썬도 마찬가지로 쓰면 될 것 같다. 많이 편하다.

예시 코드는 아래와 같다.

class Edge:
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

# 그래프 구성
n = 5  # 정점 개수
graph = [[] for _ in range(n)]
graph[0].append(Edge(1, 5))
graph[0].append(Edge(2, 3))

# 다익스트라
import heapq
start = 0  # 시작 정점 (보통 0번 또는 입력받음)
pq = [(0, start)]  # (거리, 정점)

dist = [float('inf')] * n  # 최단거리 배열
dist[start] = 0

while pq:
    cost, node = heapq.heappop(pq)
    
    if cost > dist[node]:  
        continue
        
    for edge in graph[node]:
        next_node = edge.to
        next_cost = cost + edge.weight
        
        if next_cost < dist[next_node]:
            dist[next_node] = next_cost
            heapq.heappush(pq, (next_cost, next_node))

 

다만 유의할점은 우선순위 큐가 잘 정렬되도록, 정렬 기준인 가중치를 앞에다 두어야 한다.

또한 가중치가 음수라면 다익스트라를 쓸 수 없다는 것도 기억하자.

 

사실 내용을 더 파려면 BFS/DFS도 다뤄야 하는데 그것까지 할 수는 없었다..

 

플로이드-워셜

다익스트라가 한 지점에서 다른 지점까지의 최소 거리를 구하는 방법이라면,

플로이드 워셜은 모든 정점 쌍 간의 최소 거리를 구하는 알고리즘이다.

 

그냥 말 그대로 for문 3번 돌려서 경유지 - 출발지 - 도착지의 최소값 갱신을 해주면 된다.

def floyd_warshall(graph, n):
    # 초기화 - 인접행렬 복사
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 자기 자신까지의 거리는 0
    for i in range(n):
        dist[i][i] = 0
    
    # 직접 연결된 간선들 설정
    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    for k in range(n):      # 경유지
        for i in range(n):  # 출발지
            for j in range(n):  # 도착지
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

 

 

---

이번 포스팅에선 쓱 찍먹정도만 했고,

다음 포스팅에선 BFS/DFS부터 시작해서 어떻게 크루스칼/프림/다익스트라가 동작하는지 알아보자. (시간복잡도도!)

그림을 그리면서 설명하면 참 좋은데, 필자가 워낙에 악필이라...ㅠ

 

그리고 키워드 중 트라이와 위상정렬도 있어 공부는 했는데, 제대로 이해하고 파이썬으로 구현할줄 몰라서 일단 스킵..

이것도 양을 보고 다음 포스팅에 실을 수 있으면 넣어보겠다

 

발제 끝나고 12시간 지났는데 공부한 양이 꽤 된다.

그나마 몇 번 본 개념들이라 머리에 잘 들어온 것 같다.