3. DFS & BFS

Yeonghyeon·2022년 8월 8일
알고리즘코테
0

이코테 2021

목록 보기
3/7

본 포스팅은 (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 공부하고 정리한 글임을 밝힙니다.

그래프 탐색 알고리즘: DFS/BFS

  • 탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정 ➡️ 특정 조건의 데이터가 존재하는지, 존재한다면 어느 위치에 존재하는지
  • 대표적인 그래프 탐색 알고리즘 ➡️ DFS와 BFS
    • 코딩 테스트에서 매우 자주 등장하는 유형!
  • 그래프 탐색 알고리즘 다루기 전, 반드시 알고 넘어가야 할 자료구조에 대해 먼저 알아보자

스택 자료구조

  • 먼저 들어온 데이터가 나중에 나가는 형식 (선입후출)
  • 입구와 출구가 동일한 형태 (박스 쌓기 예시 이미지)

스택 구현 예제

단순히 list 사용하면 됨 (.append(), .pop())

stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력 (즉, 제일 먼저 나가고자 하는)
print(stack) # 최하단 원소부터 출력

Out:

[1, 3, 2, 5]
[5, 2, 3, 1]

큐 자료구조

  • 먼저 들어온 데이터가 먼저 나가는 형식 (선입선출)
  • 입구와 출구가 모두 뚫려있는 터널과 같은 형태

큐 구현 예제

from collections import deque 사용하면 됨 (.append(), .popleft())

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5) # 오른쪽에 들어옴
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft() # 가장 왼쪽에 있는 데이터 꺼냄
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 변환
print(queue) # 나중에 들어온 원소부터 출력

Out:

[3, 7, 1, 4]
[4, 1, 7, 3]

재귀 함수

  • Recursive Function, 자기 자신을 다시 호출하는 함수
  • 재귀 함수의 종료 조건
    • 문제 풀이에서 사용할 때 반드시 종료 조건을 명시해야 함 (명시하지 않으면 무한 호출)

팩토리얼 구현 예제

  • n!=1×2×3×...×(n−1)×nn!=1\times 2\times 3\times ...\times (n-1)\times n
  • 수학적으로 0!0!과 1!1!의 값은 11
# 방법1. 반복적으로 구현한 n!
def factorial_iteration(n):
	result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
    	result *= 1
    return result
    
# 방법2. 재귀적으로 구현한 n!
def factorial_recursive(n):
	if n<=1: # n이 1 이하인 경우 1을 반환
    	return 1
    # n! = n * (n-1)!를 그대로 코드로 작성
    return n * factorial_recursive(n-1)
    
# 각각의 방식으로 구현한 n! 출력 (n=5)
print('반복적으로 구현:', factorial_iteratvie(5))
print('재귀적으로 구현:', factorial_recursive(5))

최대공약수 계산(유클리드 호제법) 예제

  • 유클리드 호제법: 두 개의 자연수에 대한 최대공약수를 구하는 대표 알고리즘
    - 두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R

    • 이때 A와 B의 최대공약수는 B와 R의 최대공약수 (즉, 더 낮은 값의 형태로 바꿀 수 있는 것)와 같다

  • 유클리드 호제법의 아이디어 ➡️ 재귀 함수로 작성 가능

    - 12는 6의 배수이므로 최대 공약수는 6

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

Out:

6
  • 재귀 함수 사용의 유의사항
    • 이론적으로 재귀 함수는 반복문을 이용하여 동일한 기능 구현 가능 (거꾸로도 가능)
      • 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 스택 프레임에 쌓임 ➡️ 이러한 특성으로 인해 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음 (DFS를 더 간결하게 작성하기 위해 재귀 함수 사용)
  • 깊이 우선 탐색, 깊이 부분을 우선적으로 탐색하는 알고리즘
  • 스택 자료구조(혹은 재귀 함수)를 이용
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
    2. 스택의 최상단 노드(제일 먼저 나가고자 하는 노드)에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다
    3. 더 이상 2번의 과정 수행할 수 없을 때까지 반복

DFS 동작 예시

  • Step 0. 그래프를 준비 (방문 기준: 번호가 낮은 인접 노드부터, 문제마다 방문 기준 다름)
    • 시작 노드: 1

  • Step 1. 시작 노드인 '1'을 스택에 삽입하고 방문 처리

  • Step 2. 스택의 최상단 노드인 '1'에 방문하지 않은 인접 노드 '2', '3', '8' ➡️ 이 중에서 가장 작은 노드인 '2'를 스택에 넣고 방문 처리

  • Step 3. 스택의 최상단 노드인 '2'에 방문하지 않은 인접 노드 '7' ➡️ '7'번 노드를 스택에 넣고 방문 처리 (이때 1은 이미 방문처리가 되었기 때문에 고려 x)

  • Step 4. 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '6', '8' ➡️ 이 중에서 가장 작은 노드인 '6'를 스택에 넣고 방문 처리

  • Step 5. 스택의 최상단 노드인 '6'에 방문하지 않은 인접 노드 없음 ➡️ 스택에서 '6'을 꺼냄

  • Step 6. 스택의 최상단 노드인 '7'에 방문하지 않은 인접 노드 '8' ➡️ '8'번 노드를 스택에 넣고 방문 처리

이러한 과정 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다
탐색 순서: 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

➡️ DFS는 깊이 우선으로 탐색하기때문에 그래프에서 가장 깊은 원소를 우선적으로 탐색. 더이상 깊게 들어갈 수 없다면 돌아와서 다른 방향으로 깊이 들어가는 방식

DFS 소스코드 예제

# 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 = [
  [], # 노드의 번호가 1번부터 시작하는 경우가 많기때문에 0번 인덱스는 비워둠
  [2, 3, 8], # 해당 노드(1번)에 인접한 노드 무엇인지 정렬하여 초기화
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

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

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

Out:

1 2 7 6 8 3 4 5
  • 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
  • 큐 자료구조 이용
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다
    1. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
    2. 더 이상 2번의 과정 수행할 수 없을 때까지 반복

BFS 동작 예시

매번 큐에서 원소를 꺼내, 꺼낸 원소의 인접 노드 중 방문하지 않은 노드를 모두 방문처리하는 것을 반복

  • Step 0. 그래프를 준비 (방문 기준: 번호가 낮은 인접 노드부터, 문제마다 방문 기준 다름)

    - 시작 노드: 1

  • Step 1. 시작 노드인 '1'을 큐에 삽입하고 방문 처리

  • Step 2. 큐에서 노드 '1'을 꺼내 방문하지 않은 인접 노드 '2', '3', '8'을 큐에 삽입하고 방문 처리 (인접 노드 중 작은 번호부터 넣는다 가정)

  • Step 3. 큐에서 노드 '2'를 꺼내 방문하지 않은 인접 노드 '7'을 큐에 삽입하고 방문 처리

  • Step 4. 큐에서 노드 '3'을 꺼내 방문하지 않은 인접 노드 '4', '5'를 큐에 삽입하고 방문 처리

  • Step 5. 큐에서 노드 '8'을 꺼내 방문하지 않은 인접 노드가 없으므로 무시

이러한 과정 반복하였을 때 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다
탐색 순서: 1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

➡️ 시작 노드 '1'에서 거리가 1인 노드 모두 방문 후에, 거리가 2인 노드 모두 방문, 그리고 거리가 가장 먼 '6'번 노드를 가장 마지막에 방문
➡️ 각 간선의 비용이 모두 동일한 상황에서 최단 거리 문제를 해결하기 위한 목적으로도 사용됨

BFS 소스코드 예제

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐 구현 위해 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)

Out:

1 2 3 8 7 4 5 6

DFS & BFS 기초 문제 풀이

<문제> 음료수 얼려 먹기

문제 설명:

문제 해결 아이디어

  • 위 그림처럼 얼음을 얼릴 수 있는 공간이 상, 하, 좌, 우로 연결되어 있다고 표현하여 그래프 형태로 모델링 가능

  • 특정 지점에서 DFS or BFS 활용하여 이동할 수 있는(0) 모든 경우에 대해서 방문 처리를 진행하도록 처리

DFS를 이용한 알고리즘

  1. 특정 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문
  2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행한 과정을 반복하면, 연결된 모든 지점을 방문 가능
  3. 모든 노드에 대하여 1~2번 과정을 반복하면서, 방문하지 않은 지점의 수를 카운트

DFS 답안 예시

# 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을 공백 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

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

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

print(result) # 정답 출력

그래프에서 해당 노드가 0인 경우에는 True를 반환하므로 카운트가 됨 (이때 인접한 노드들로 재귀 호출하여 중 0인 노드가 있을 때 1로 바꾸어주기 때문에, 원본 그래프에서 0이 었던 노드들을 반복문을 통해 DFS 함수를 호출했을 때 True가 아닌 False를 반환하므로 이중 카운트 되지 않는 것)
해당 노드가 1인 경우에는 DFS 함수에서 첫 조건문에 의해 바로 False를 반환하므로 카운트 되지 않음

즉, 그래프에서 해당 노드가 0인 경우에는 다 카운트 되는 것

<문제> 미로 탈출

문제 설명:

-> 0인 경우에 괴물이 존재 (0을 피해 (n,m)까지의 최단 길이 구하는 문제)

BFS를 이용한 문제 해결 아이디어


  • 인접한 노드 중 값인 1인 경우에만 이동 가능하도록

BFS 답안 예시

# BFS 소스코드 구현
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]
  
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를 수행한 결과 출력
print(bfs(0, 0))
profile
Yeonghyeon
이전 포스트

2. 그리디 & 구현

다음 포스트

4. 정렬 알고리즘

0개의 댓글

관련 채용 정보