원글 페이지 : 바로가기
그래프 그래프는 현상이나 사물을 정점(Vertex) 또는 노드(Node), 간선(Edge)으로 표현하기 위해 사용한다. – 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 – 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함(Link 또는 Branch라고도 함) – 인접 정점(Adjacent Vertext) : 간선으로 직접 연결된 Vertex(또는 Node) 1) 무방향 그래프(undirected graph) – 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음 – 보통 노드 A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)로 표기 2) 방향 그래프(directed graph) – 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 있음 – 노드 A->B로 연결되어 있을 경우
def __init__(self, item, left, right):
# item은 본인(root node가 됨), left, right는 각각 child node가 됨
self.item = item
self.left = left
self.right = right
def preorder(node):
print(node.item, end=””)
if node.left != ‘.’:
preorder(tree[node.left])
if node.right != ‘.’:
preorder(tree[node.right]) 2. Inorder traverse(중위 순회): 왼쪽 자식 노드 방문 => 노드 자신을 방문 => 오른쪽 자식 노드 방문 왼쪽 자식 노드를 먼저 처리한 다음, 뒤이어 자기 자신을 처리한다. 그 다음에 오른쪽 자식 노드를 방문한다. class Node:
def __init__(self, item, left, right):
# item은 본인(root node가 됨), left, right는 각각 child node가 됨
self.item = item
self.left = left
self.right = right
def inorder(node):
if node.left != ‘.’:
inorder(tree[node.left])
print(node.item, end=””)
if node.right != ‘.’:
inorder(tree[node.right]) 3. Postorder traverse(후위 순회): 오른쪽 자식 노드 방문 => 왼쪽 자식 노드 방문 => 노드 자신을 방문 마지막 순회인 후위 순회는 왼쪽 자식 노드를 방문한 다음, 오른쪽 자식 노드까지 방문을 다 마치고 자기 자신을 방문하는 순서로 순회한다. class Node:
def __init__(self, item, left, right):
# item은 본인(root node가 됨), left, right는 각각 child node가 됨
self.item = item
self.left = left
self.right = right
def postorder(node):
if node.left != ‘.’:
postorder(tree[node.left])
if node.right != ‘.’:
postorder(tree[node.right])
print(node.item, end=””) 1. 1991: 트리 순회 [풀이 1] 전체적인 구성은 똑같고 출력 위치만 바꿔주면 된다. if(left)/if(right)/print(자기자신)의 순서만 다르기 때문에 이에 유념해서 클래스를 생성해 코드는 짜면 된다. 입력값을 받을 때는 tree라는 딕셔너리를 만들고, N번만큼 for문을 돌려 node, left, right를 map 함수를 이용해서 각각 나눈다. tree의 key값에 node를 넣고, class Node를 이용해서 node, left, right를 정의해준다. # 1991: 트리 순회
import sys
sys.stdin = open(“input.txt”,”r”)
class Node:
def __init__(self, item, left, right):
# item은 본인(root node가 됨), left, right는 각각 child node가 됨
self.item = item
self.left = left
self.right = right
def preorder(node):
print(node.item, end=””)
if node.left != ‘.’:
preorder(tree[node.left])
if node.right != ‘.’:
preorder(tree[node.right])
def inorder(node):
if node.left != ‘.’:
inorder(tree[node.left])
print(node.item, end=””)
if node.right != ‘.’:
inorder(tree[node.right])
def postorder(node):
if node.left != ‘.’:
postorder(tree[node.left])
if node.right != ‘.’:
postorder(tree[node.right])
print(node.item, end=””)
if __name__ == “__main__”:
N = int(sys.stdin.readline())
tree = {}
for i in range(N):
node, left, right = map(str, sys.stdin.readline().split())
tree[node] = Node(item=node, left=left, right=right)
preorder(tree[‘A’])
print()
inorder(tree[‘A’])
print()
postorder(tree[‘A’]) [풀이 2] 전위, 중위, 후위 순회의 코드 자체는 별다를게 없지만 입력받는 부분이 살짝 다른다. 1) 먼저 nodes라는 딕셔너리를 만든다. 이는 방법 1에서 만든 tree 딕셔너리와 똑같은 역할을 한다. 2) 방법2에서는 class Node를 사용하지 않고, nodes의 키 값에 temp[0] 즉, root를 넣어주고, 리스트안에 차례대로 자식 노드들을 넣어준다. => 즉, node를 key로 한 뒤, 해당 node에 연결된 node들을 리스트로 만들어 value로 추가한다. 딕셔너리를 출력해보면 키와 키 값에 해당하는 value 값이 들어간 것을 볼 수 있다. # 1991: 트리순회
import sys
sys.stdin = open(‘input.txt’, ‘r’)
input = sys.stdin.readline
# print = sys.stdout.write
n = int(input())
nodes = dict()
for _ in range(n):
temp = input().split()
# nodes라는 딕셔너리의 key 값에 root가 들어가고, value에 리스트 형태로 자식 노드들이 들어감
nodes[temp[0]] = [temp[1], temp[2]]
# 딕셔너리의 키-값 쌍으로 출력하는 방법
# for key, value in nodes.items():
# print(key, value)
def preorder(root): # 전위순회
if root == ‘.’:
return
print(f'{root}’, end=””)
preorder(nodes[root][0])
preorder(nodes[root][1])
def inorder(root): # 중위순회
if root == ‘.’:
return
inorder(nodes[root][0])
print(f'{root}’, end=””)
inorder(nodes[root][1])
def postorder(root): # 후위순회
if root == ‘.’:
return
# nodes[root][0]와 nodes[root][1]는 root의 자식노드 !
postorder(nodes[root][0]) # 왼쪽 자식 노드
postorder(nodes[root][1]) # 오른쪽 자식 노드
print(f'{root}’, end=””) # 노드 방문
# temp[0] == ‘A’ 일 때~
preorder(‘A’)
print()
inorder(‘A’)
print()
postorder(‘A’) 공부 참고 블로그: From WH: https://velog.io/@wonhee/%EC%9D%B4%EC%A7%84%EA%B2%80%EC%83%89%ED%8A%B8%EB%A6%AC-%EB%BF%8C%EC%8B%9C%EA%B8%B0 그래프 설명: https://velog.io/@jewon119/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89BFS-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS # 2022/10/22 복습 코드
# 1991: 트리 순회
# 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드
import sys
from collections import defaultdict
sys.stdin = open(“RETRY/트리순회/input.txt”,”r”)
input = sys.stdin.readline
def preorder(root): # 전위 순회: 노드 자신을 방문 => 왼쪽 자식 노드 방문 => 오른쪽 자식 노드 방문
if root == ‘.’:
return
print(f'{root}’, end=””)
preorder(graph[root][0]) # graph의 root 노드의 왼쪽 자식
preorder(graph[root][1]) # graph의 root 노드의 오른쪽 자식
def inorder(root): # 중위 순회: 왼쪽 자식 노드 방문 => 노드 자신을 방문 => 오른쪽 자식 노드 방문
if root == ‘.’:
return
inorder(graph[root][0])
print(f'{root}’, end=””)
inorder(graph[root][1])
def postorder(root): # 후위 순회: 왼쪽 자식 노드 방문 => 오른쪽 자식 노드 방문 => 노드 자신을 방문
if root == ‘.’:
return
postorder(graph[root][0])
postorder(graph[root][1])
print(f'{root}’, end=””)
# N: 이진 트리의 노드의 개수
N = int(input().rstrip())
graph = defaultdict(list)
for i in range(N):
# graph라는 딕셔너리의 key값에 root가 들어가고, value에 리스트 형태의 자식 노드들이 들어감.
tmp = list(input().split())
graph[tmp[0]].append(tmp[1])
graph[tmp[0]].append(tmp[2])
# graph를 defaultdict로 선언했기 떄문에 graph를 출력하면
# defaultdict(
# print(graph[‘A’])를 출력하면 [‘B’, ‘C’]의 결과가 나온다. so, root의 값을 ‘A’로 준다.
preorder(‘A’)
print()
inorder(‘A’)
print()
postorder(‘A’)