그래프 / 트리 / 이진트리 : 모두 구분할 수 있어야 한다.
개념 및 입력
그래프의 표현 방식에는 2가지가 있다.
- 인접행렬 방식
- 인접 리스트 방식
그래프는 기본적으로 1-indexed를 사용한다.
예시 그래프
방향 있음. (없는 경우 그냥 맞춰서 해주면 되서 상관없음)
5
7
3 1
2 3
4 1
5 2
5 4
3 5
2 4
- 인접 행렬
두 정점의 연결여부를 확인하는게 잦은 경우 자주 쓰인다.
E가 V**2에 가까울 때
두 정점 사이의 연결을 살필때 : O(1)
정점을 V개에 연결된 모든 정점을 살피려면 : O(V)
공간은 V**2만큼 필요함.
받는 방식
import sys
n = int(input())
e = int(input())
mat = [[0]*(n+1) for _ in range(n+1)]
for i in range(e):
s, end = map(int, (sys.stdin.readline().strip().split()))
mat[s][end] = 1
# mat[end][s] = 1 무방향
print(mat)- 인접 리스트
특정 정점에 대한 모든 연결정점을 확인할 때 주로 쓰인다.
정점은 많고 간선은 상대적으로 작은 상황에 쓰인다.(E가 V**2보다 현저히 작을때)
정점이 V 간선이 E인경우 공간은 (V+E)만큼 필요.
실제 리스트로 구현하는게 아니라 벡터를 저장하는 방식으로 많이 쓰인다.
두 정점u,v 사이의 연결을 살필때 : O(min(차수[u],[v])) > 어차피 리스트를 흝어야 하지만
기왕 흝을 거 차수가 더 작은것에서 전체를 살피는게 이득이기 때문
정점을 V개에 연결된 모든 정점을 살피려면 : O(차수[v])
받는 방식
import sys
n = int(input())
e = int(input())
mat = [[] for _ in range(n+1)]
for i in range(e):
s, end = map(int, (sys.stdin.readline().strip().split()))
mat[s].append(end)
#mat[end].append(s) 무방향
print(mat)트리
트리도 그래프의 일종이다.
무방향이면서 사이클이 없는 연결그래프
서로 다른 두점을 연결하는 간선이 최대 1개인 그래프 (E = V-1) 정점간의 간선은 하나.
임의의 노드를 루트로 만들수 있다.(구슬간의 연결을 들어올린다고 생각하면 됌)
*정점이 한개고 간선이 없는 그래프도 트리임. (노드 하나)
-BFS in 트리
- 부모 배열 채우는 방식 : 부모정보가 필요한 문제는 다음과 같이 풀어줄 수 있다.
부모는 이미 방문한 상태일 것이니 큐에는 자식만 넣어준다.
보통은 큐에 넣고 방문처리를 하는 것이 습관이나, 최초의 start는 처리하지 않고 있음을 유의한다
(>>>>> q.appendleft(start) 이후 방문처리는 하지 않음으로 p[start]는 초기화 하지않음으로서 0값을 만드는 것을 알 수 있다.)
import sys
from collections import deque
n = int(input())
e = int(input())
mat = [[] for _ in range(n+1)]
for i in range(e):
s, end = map(int, (sys.stdin.readline().strip().split()))
mat[s].append(end)
mat[end].append(s)
####받아오기 위의 입력받는 것과 동일함
p = [0]*(n+1) #부모들의 정보를 가진 배열 p[2] = 3 >>> 2번 노드의 부모는 3번노드임
def bfs(start):
q = deque()
q.appendleft(start) #p[start] = 0으로 루트임을 알수 있겠다.
while(q):
cur = q.pop()
for nxt in mat[cur]:
if p[cur] == nxt: #부모인경우
continue
q.appendleft(nxt)
p[nxt] = cur #nxt가 내 자식인거니 부모를 넣어줌
- 부모와 depth배열 채우기 >>> 자식의 depth는 부모 depth+1 임을 이용한다
위와 같은 방식이나, depth가 추가되었다
p = [0]*(n+1) #부모들의 정보를 가진 배열 p[2] = 3 >>> 2번 노드의 부모는 3번노드임
depth = [0]*(n+1)
def bfs(start):
q = deque()
q.appendleft(start) #p[start] = 0으로 루트임을 알수 있겠다.
while(q):
cur = q.pop()
for nxt in mat[cur]:
if p[cur] == nxt: #부모인경우
continue
q.appendleft(nxt)
p[nxt] = cur #nxt가 내 자식인거니 부모를 넣어줌
depth[nxt] = depth[cur] + 1-DFS in 트리
- 비재귀 방식 : 부모배열, depth 채우기
### 위에 mat 받아오고
p = [0]*(n+1)
depth = [0]*(n+1)
def dfs(start):
stack = []
stack.append(start) #
while(stack):
cur = stack.pop()
for nxt in mat[cur]:
if p[cur] == nxt:
continue
stack.append(nxt)
p[nxt] = cur
depth[nxt] = depth[cur]+1- 재귀 방식 : 부모, depth 채우기
####받아오고
p = [0]*(n+1)
depth = [0]*(n+1)
def dfs(node):
for nxt in mat[node]:
if p[node] == nxt:
continue
p[nxt] = node
depth[nxt] = depth[node]+1
dfs(nxt)- 저장 없이 단순 순회 : 재귀
def dfs(node, p):
for nxt in mat[node]:
if nxt == p:
continue
dfs(nxt,node)이진트리
이진트리에서의 순회는 4가지가 있다.
[level / 전위 / 중위 / 후위] 순회
클래스 구현으로 할 수도 있으나 배열 주로 사용.
세팅
왼쪽 자식과 오른쪽 자식을 구분하기 위함.
사진 출처 : 바킹독 알고리즘 강의 (유튜브) (🙏🙏🙏) > 링크
- 레벨 순회
####lc,rc의 방법으로 받아오고.
lc = [0,2,4,6,0,0,0,0,0] #### 받아왔다고 칠 때
rc = [0,3,5,7,0,8,0,0,0]
def dfs(root): #위의 그림에서 root=1
q = deque()
q.appendleft(root)
while(q):
cur = q.pop()
if lc[cur]:
q.appendleft(lc[cur])
if rc[cur]:
q.appendleft(rc[cur])- 전위 순회 (level을 제외한 순회는 재귀적으로 함)
- 현재 정점을 방문한다.
- 왼쪽 서브트리를 전위 순회 한다.
- 오른쪽 서브트리를 전위 순회 한다.
부모부터 시작해 왼쪽자식 > 오른쪽 자식으로 긁는 형국
*결국 전위순회는 DFS와 동일한 구조임
def preorder(cur):
print(cur)
if lc[cur]:
preorder(lc[cur])
if rc[cur]:
preorder(rc[cur])
- 중위 순회
- 왼쪽 서브트리를 중위 순회 한다. (방문하지 않음)
- 현재 정점을 방문한다.
- 오른쪽 서브트리를 중위 순회 한다.
가장 왼쪽 자식부터 모으고 자신을 보고 오른쪽 자식을 보는 형국
def inorder(cur):
if lc[cur]:
inorder(lc[cur])
print(cur)
if rc[cur]:
inorder(rc[cur])- 후위 순회
- 왼쪽 서브트리를 후위순회 한다.
- 오른쪽 서브트리를 후위순회한다.
- 현재 정점을 방문한다.
자식들을 다 긁고 나서 자신을 보는 형국
def postorder(cur):
if lc[cur]:
postorder(lc[cur])
if rc[cur]:
postorder(rc[cur])
print(cur)서로 다른 트리여도 순회의 결과는 같을 수 있다.
