유튜브 참고

스택

• 선입후출: 박스 쌓기
• 리스트 선언 후 append()와 pop()으로 구현
• 컴퓨터 메모리 내부에 쌓이므로 스택을 사용해야할 때 구현상 재귀함수를 이용하는 경우가 많음

큐

• 선입선출: 줄 서있는 사람들
• deque 라이브러리 사용 필요 -> append()와 popleft()로 구현
• 리스트로도 사용할 수 있지만, pop 시 요소를 앞 인덱스로 하나씩 당겨오는 작업이 생겨 비효율적이며 O(n)만큼의 시간복잡도 발생 -> 덱을 이용하자.

from collections import deque

재귀함수

예시 문제: GCD - 유클리드 호제법

코드

def gcd (a, b):
  if a % b== 0:
    return b
  else:
    return gcd(b, a % b)
    
print(gcd(192, 162))

함수의 동작 구조 상 a와 b의 크기에 따른 순서는 상관이 없다.

DFS: 깊이 우선 탐색

• 깊은 부분 우선적으로 탐색
• 스택 자료구조 or 재귀함수 이용

코드

# DFS 메서드 정의
def dfs(graph, v, visited):
  # 현재 노드를 방문 처리
  visited[v] = True
  print(v, end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs (graph, i, visited)
      
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7], 
  [1, 4, 5], 
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

BFS: 너비 우선 탐색

• 가까운 노드부터 탐색 -> 간선의 비용이 모두 같을 때 최단거리 찾기 위해 사용
• 큐 자료구조 이용

코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    print(v, end='")
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append (i)
        visited[i] = True
        
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7], 
  [1, 4, 5], 
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

---

예시 문제 1: 음료수 얼려 먹기

코드

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
  # 주어진 범위를 벗어나는 경우에는 즉시 종료
  if x <= -1 or x >= N or y <= -1 or y >= M:
    return False

  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 0:
    # 해당 노드 방문 처리
    graph[x][y] = 1
    # 상하좌우의 위치들도 모두 재귀적으로 호출
    dfs(x - 1, y)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x, y + 1)
    return True
  return False

N, M = map(int, input().split())

graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

result = 0
for n in range(N):
  for m in range(M):
    # 현재 위치에서 dfs 수행
    if dfs(n, m) == True:
      result += 1

print(result)

예시 문제 2: 미로 탈출

코드

from collections import deque

def bfs(x, y):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque()
  queue.append((x, y))

  # 큐가 빌 때까지 반복하기
  while queue:
    x, y = queue.popleft()
    # 현재 위치에서 4가지 방향으로서의 위치 확인
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 미로 찾기 공간을 벗어난 경우 무시
      if nx < 0 or nx >= N or ny < 0 or ny >= M:
        continue
      # 벽인 경우 무시
      if graph[nx][ny] == 0:
        continue
      # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))
  # 가장 오른쪽 아래까지의 최단 거리 반환
  return graph[N - 1][M - 1]


N, M = map(int, input().split())

graph = []
for _ in range(N):
  graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 - 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(0, 0))