24.01.21 백준 1191,5639,1197,2606,1260

백준

1191 트리 순회

• 트리 전위순회, 중위순회, 후위순회
• 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
• 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
• 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문

import sys

n = int(sys.stdin.readline())
tree = {}

for i in range(n):
	root, left, right = map(int,sys.stdin.readline().split())
	tree[root] = [left, right]

def preorder(root):
	if root != '.':
		print(root,end='')
		preorder(tree[root][0])
		preorder(tree[root][1])

def inorder(root):
	if root != '.':
		inorder(tree[root][0])
		print(root,end='')
		inorder(tree[root][1])

def postorder(root):
	if root != '.':
		postorder(tree[root][0])
		postorder(tree[root][1])

preorder('A')
print()
inorder('A')
print()
postorder('A'

5639 이진 검색 트리

• try except 구문 활용, while 탈출
• sys.setrecursionlimit(10 ** 5)

import sys
sys.setrecursionlimit(10**5)
pre = []

while True:
	try:
		pre.append(int(sys.stdin.readline()))
	except:
		break

def postorder(start,end):
	if start > end:
		return
	mid = end + 1
	for i in range(start+1, end+1):
		if pre[start] < pre[i]:
			mid = i
			break
	postorder(start + 1, mid -1)
	postorder(mid ,end)
	print(pre[start])

postorder(0,len(pre)-1)

1197 최소 스패닝 트리_MST

• Kruskal
• union_find
  • 그래프 알고리즘 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘
  • 서로소 집합, 상호 배타적 집합(Disjoint-set)으로도 불린다.
  • 노드를 합치는 union연산과 노드의 루트 노드를 찾는 find연산으로 이루어진다.

import sys
sys.setrecursionlimit(10**9)

v,e = map(int,sys.stdin.readline().split())

edge = []
for i in range(e):
	a, b, w = map(int,sys.stdin.readline().split())
	edge.append((a,b,w))
edge.sort(key = lambda x: x[2])

parent = [i for in range(v+1)]

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

def union_parent(a,b):
	a = find(a)
	b = find(b)

	if a<b:
		parent[b] = a
	else:
		parent[a] = b

def same_parent(a,b):
	return find(a) == find(b)

ans = 0
for a,b,w in edge:
	if not same_parent(a,b):
		union_parent(a,b)
		ans += w
print(ans)

2606 바이러스

import sys
sys.setrecursionlimit(10**5)

def search(start)
	for i in range(n):
		if network[start][i] == 1 and i not in cnt:
			cnt.add(i)
			search(i)
cnt = set()
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
network[[0 i in range(n)] for i in range(n)]
for i in range(m):
	a, b = map(int, sys.stdin.readline().split())
	network[a-1][b-1] = 1
	network[b-1][a-1] = 1

search(0)
if len(cnt) == 0:
	print(0)
else:
	print(len(cnt)-1)

1260 DFS와 BFS

• 그래프 인접리스트로 구현
• DFS 재귀함수로 구현
• BFS 큐로 구현 collections deque 이용

import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)

def dfs(v):
	print(v,end=' ')
	visited[v] = True
	for e in adj[v]:
		if not(visited[e])
			dfs(e)
def bfs(v):
	q = deque([v])
	while q:
		v = q.popleft()
		if not (visited[v]):
			visited[v] = True
			print(v, end = ' ')
			for e in adj[v]:
				if not visited[e]:
					q.append(e)

v, e, start = map(int,sys.stdin.readline().split())
adj = [[]for i in range(v+1)]
for i in range(e):
	a,b = map(int,sys.stdin.readline().split())
	adj[a].append(b)
	adj[b].append(a)
for i in adj:
	i.sort()

visited = [False]*(v+1)
dfs(start)
print()
visited = [Fasle]*(v+1)
bfs(start)

• 내 손으로 풀은 문제가 매우 매우 적다. 단 한개.. 그래도 점점 컴퓨팅적 사고로 바뀌어가고 있다고 믿어 의심치 않는다. 다음 날, 그 다음 날에는 더 많이 성장해 있겠지. 힘들지만 파이팅!