스택, 큐, 재귀함수와 그래프

이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다.

스택

stack = []
stack.append(2)
stack.append(3)
stack.pop()
stack.append(5)

print(stack)
print(stack[::-1])  #최상단 원소부터 출력

따로 import할 필요 없이 일반 리스트라고 생각하면 됨

큐

from collections import deque

queue=deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
queue.append(1)
queue.popleft()

print(queue)

#나중에 들어온 원소부터 출력하려면 (거꾸로 출력)
queue.reverse()
print(queue)

#리스트로 바꾸고 싶으면
list(queue)

from collections import deque 와 queue.popleft()를 기억하자!

큐가 빌 때까지 반복하려면?

while queue:
   queue.popleft()
   #코드...

재귀함수

팩토리얼 예제

 def factorial_recursive(n):
   if n<=1:
      return 1
   return n* factorial_recursive(n-1)

재귀 함수의 종료 조건을 꼭 명시하자.

---

DFS는 스택과 재귀함수가 키워드
BFS는 큐가 키워드

일반적으로 BFS가 수행 시간이 더 좋음.

예제: 백준 1260

https://www.acmicpc.net/problem/1260

 from collections import deque

def BFS(start):
  queue=deque()
  queue.append(start)
  visited2[start]=True
  
  while queue:
    v=queue.popleft()
    print(v, end=' ') #줄바꿈 없이 공백 기준으로 출력
    for i in range(n+1):      
      if graph[v][i]==1 and visited2[i]==False:     
        queue.append(i)
        visited2[i]=True


def DFS(v):   
  visited[v]=True
  print(v, end=' ')
 
  for i in range(n+1):
    if graph[v][i]==1 and visited[i]==False:     
      DFS(i)
    
  


n,m,start=list(map(int,input().split()))
graph = [[0]*(n+1) for _ in range(n + 1)]

for i in range(m):
  a,b=map(int,input().split())
  graph[a][b]=1
  graph[b][a]=1

visited=[False]*(n+1)
DFS(start)

print()

visited2=[False]*(n+1)
BFS(start)

기타 기억해야 할 요소

리스트 컴프리헨션을 이용한 리스트 초기화

graph = [[0]*(n+1) for _ in range(n + 1)]

visited=[False]*(n+1)

참고: 이코테 124p~148p