[알고리즘] 7. 그래프 탐색

Index

1. 스택과 큐

2. 재귀

3. 유클리드 호제법

4. DFS

5. BFS

6. 추천 문제

7. 참고자료

---

- Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

- 그래프 탐색 알고리즘으로 DFS/BFS가 있음

 

1. 스택과 큐

Stack

- FILO(First In Last Out)의 자료구조

- 입구와 출구가 동일

stack = []

# 삽입
stack.append(val)

# 삭제
stack.pop()

# 최상단 원소 확인
print(stack[-1])

Queue

- FIFO(First In First Out)의 자료구조

- 입구와 출구가 양쪽으로 나있는 터널 형태

queue = []

# 삽입
queue.append(val)

# 삭제
queue.pop(0)

# 최하단/최상단 원소 확인
queue[0]
queue[-1]​

Deque

- 양방향 모두 삽입 삭제가 가능한 자료구조

from collections import deque

dq = deque()

# 삽입
dq.append(val)

# 삭제
dq.popleft()

# 최하단/최상단 원소 확인
dq[0]
dq[-1]

 

2. 재귀

Recursive Function

- 자기 자신을 다시 호출하는 함수

- 반드시 base condition(종료조건)이 필요

- 모든 재귀 함수는 반복문을 이용하여 동일한 기능 구현이 가능

def func_name(params, ...):
  if base_condition:
    return val
  ...
  func_name(...)
  ...
  return

 

Factorial

- n! = 1 x 2 x 3 x ... x (n-1) x n

# 반복문 구현
def fac_it(n):
  result = 1
  for i in range(1, n+1):
    result *= i
  return result
  
# 재귀 구현
def fac_re(n):
  if n <= 1:
    return 1
  else:
    return n*fac_re(n-1)

 

3.  유클리드 호제법

유클리드 호제법

- 두개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘

- 두 자연수 A, B(A > B)에 대하여 A를 B로 나눈 나머지를 R이라고 할 때, A와 B의 최대 공약수는 B와 R의 최대공약수와 같다.

def gcd(a, b):
  if a < b:
    a, b = b, a
  if a % b == 0:
    return b
  else:
    return gcd(b, a%b)

 

4. DFS

DFS(Depth-First Search)

- 깊이 우선 탐색은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택 자료구조(재귀 함수)를 이용

 

(동작 과정)

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리

2-1) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리

2-2) 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄

3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

def dfs(graph, node, visited):
  visited[node] = True
  for i in graph[node]:
    if not visited[i]:
      dfs(graph, i, visited)
      
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5]
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * len(graph)

dfs(graph, 1, visited)

 

5.  BFS

BFS(Breadth-Frist Search)

- 너비 우선 탐색은 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

- 큐 자료구조를 이용

 

(동작 과정)

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리

2) 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큥에 삽입하고 방문 처리

3) 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

from collections import deque

def bfs(graph, start, visited):
  q = deque([start])
  visited[start] = True
  while queue:
    v = q.popleft()
    for i in graph[v]:
      if not visited[i]:
        quequ.append(i)
        visited[i] = True
  
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5]
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * len(graph)
bfs(graph, 1, visited)

 

6.  추천 문제

DFS/BFS

- 케빈 베이컨의 6단계 법칙(https://www.acmicpc.net/problem/1389)

- DFS와 BFS(https://www.acmicpc.net/problem/1260)

- 바이러스(https://www.acmicpc.net/problem/2606)

- 토마토(https://www.acmicpc.net/problem/7576)

- 타겟 넘버(https://school.programmers.co.kr/learn/courses/30/lessons/43165)

- 게임 맵 최단거리(https://school.programmers.co.kr/learn/courses/30/lessons/1844)

- 네트워크(https://school.programmers.co.kr/learn/courses/30/lessons/43162)

- 여행 경로(https://school.programmers.co.kr/learn/courses/30/lessons/43164)

- 단어 변환(https://school.programmers.co.kr/learn/courses/30/lessons/43163)

- 아이템 줍기(https://school.programmers.co.kr/learn/courses/30/lessons/87694)

- 퍼즐 조각 채우기(https://school.programmers.co.kr/learn/courses/30/lessons/84021)

---

참고 자료

[Youtube: 동빈나의 이코테 2021(DFS/BFS)] https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4