➕ 나동빈님 이코테에서 들은 내용을 기반으로 정리하고 공부한 게시글입니다.

✔ 탐색이란?

탐색(search)는 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

• 스택 자료구조 : 선입후출, 입구와 출구가 동일한 형태로 스택 시각화
  (💻python - 리스트, 삽입 : append(), 삭제 : pop())

• 큐 자료구조 : 선입선출, 입구와 출구가 모두 뚫려있는 터널 형태로 스택 시각화
  (💻python - deque 라이브러리, 삽입 : append(), 삭제 : popleft())

• 재귀함수(recursive function) : 자기 자신을 다시 호출하는 함수
  -> 종료 조건을 넣어주어 함수가 무한이 호출되는 것을 방지
  1. 팩토리얼 예제

  # 반복적으로 구현한 n!
  def factorial_iterative(n):        
      result = 1
      # 1부터 n까지의 수를 차례대로 곱하기
      for i in range(1, n + 1):
         result *= i
      return result
  
  # 재귀적으로 구현한 n!
  # 코드가 더 간결함
  def factorial_recursive(n):        
      if n <= 1: # n이 1 이하인 경우 1을 반환
          return 1
      return n * factorial_recursive(n - 1) #재귀적
  
  # 각각의 방식으로 구현한 n! 출력(n = 5)
  print('반복적으로 구현:', factorial_iterative(5))
  print('재귀적으로 구현:', factorial_recursive(5))

  2. 최대공약수(GCD) 계산(유클리드 호제법) 예제
     : 두 자연수 A,B(A>B)에 대하여 A를 B로 나눈 나머지는 R이다. 이 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

     👉 문제해결과정

     1. A와 B의 최대공약수는 B와 R의 최대공약수와 같으니까
     2. A를 B로 나누어 나머지 R을 B자리에 넣는다.
     

     def gcd(a,b):
         if a % b === 0:
             return b
         else:
             return gcd(b, a%b) # a%b = R
     
     print(gcd(102, 162)) #6

✔ DFS(Depth-First Search)이란?

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조(혹은 재귀 함수)를 이용한다.

👉 문제해결과정

시작 노드 : 1, 방문 기분 : 번호가 낮은 인접노드부터

# 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번노드와 인접한 노드 2,3,8
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 1~8번 노드가 있어야 하니까 9개(0번 노드를 사용하지 않을꺼라)

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

✔ BFS(Breadth-First Search)이란?

너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 큐 자료구조를 이용하다.

👉 문제해결과정

시작 노드 : 1, 방문 기분 : 번호가 낮은 인접노드부터

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번노드와 인접한 노드 2,3,8
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9 # 1~8번 노드가 있어야 하니까 9개(0번 노드를 사용하지 않을꺼라)

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

✔ 문제1 : 음료수 얼려 먹기

N X M 크기의 얼음틀에 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1입니다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우는 서로 연결되어 있습니다. 이때, 얼음 틀의 모양에서 생성(0에 을료수를 부어서)되는 총 아이스트림의 개수를 구하는 프로그램을 작성하시오.

👉 문제해결과정

• 연결리스트 찾기
• DFS

1. 노드가 0일때, 인접해있는 노드 중에서 방문하지 않은 0끼리 연결한다.
2. 노드가 1일때, 인접해있는 노드 중에서 방문하지 않은 0에 방문한다.
3. 방문하지 않은 지점의 수를 카운트

if 4 X 5 얼음틀에서는 아이스크림이 총 3개

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 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

# 모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행
        if dfs(i, j) == True:
            result += 1

print(result) # 정답 출력

✔ 문제2 : 미로 탈출

N X M 크기의 미로에서 (1,1) 위치에서 (N,M) 출구로 탈출해야한다. 한 번에 한 칸씩 이동할 수 있으며 괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다. 미로를 탈출하기 위한 최소 횟수를 구하시오(단, 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.)

👉 문제해결과정

• 연결리스트 찾기
• BFS

1. 시작 노드에서 BFS로 가까운 노드 중 1인 노드에 방문한다.
2. 노드가 이동하면 이동한 노드이 값을 count++ 로 바꾼다.
3. 이동한 노드의 값을 큐에서 꺼내 1~2번을 반복한다.

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

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

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 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]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

🌱 결론

탐색 알고리즘은 여러 문제에 활용이 가능하다. 스택, 큐, 재귀함수에 대한 개념을 탄탄히 하고 알고리즘 코드를 더 공부해야겠다!