코딩 테스트 준비 기록 - Day 4

BFS / DFS Algorithm

탐색이란?

많은 양의 데이터 중 원하는 데이터를 찾는 과정
BFS / DFS : 대표적인 그래프 탐색 알고리즘

💡 반드시 알아야 할 자료구조 및 개념

1. stack
   • Last in First Out
   • 입구와 출구가 동일한 형태
   • 삽입과 삭제 연산으로 이루어졌으며 각각의 시간복잡도는 O(1)
   • Python에서는 List 자료형을 Stack 처럼 사용 (append, pop)
2. queue
   • First in First Out
   • 입구와 출구가 모두 뚫려있는 터널 같은 형태
   • 삽입과 삭제 연산으로 이루어졌으며 각각의 시간복잡도는 O(1)
   • Python에서는 Deque 자료형을 Queue 처럼 사용 (append, pop_left)
3. 재귀 함수(Recursive Function)
   • 자기 자신을 다시 호출하는 함수
     ❗재귀 함수의 종료조건을 명시하여 무한히 호출되는 문제를 막아야 한다.
   • 유클리드 호제법(최대 공약수 구하는 대표 알고리즘)
     • 두 자연수 A,B(A>B)에 대해 A를 B로 나눈 나머지를 R이라고 하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.
   • 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있으나, 다른 사람이 이해하기 어려울 수 있으므로 주의
   • 반복문과 재귀 함수는 상호 변경 가능
   • 컴퓨터가 재귀 함수를 여러번 호출하면 메모리 내부의 스택 프레임에 쌓임
     • 스택을 사용해야할 때 (DFS) 재귀 함수를 이용하는 경우가 많음.

DFS

• 깊이를 우선으로 하여 탐색하는 알고리즘
• 스택 구조 OR 재귀 함수를 이용함
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택의 최상단 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 스택에 넣고 방문 처리, 없으면 스택에서 꺼냄.
  3. 2과정 반복

BFS

• 너비를 우선으로 하여 탐색하는 알고리즘 (graph 내에서 가까운 노드부터 탐색하는 알고리즘)
• Queue 자료구조 이용함
• 동작 과정
  1. 탐색 시작 노드를 queue에 담고 방문 처리
  2. 큐에서 노드를 1개 꺼내고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 queue에 삽입하고 방문처리
  3. 2과정 반복

💡 문제 1. 음료수 얼려먹기

• 구분된 곳의 개수를 찾는 문제
• 탐색하는 dfs를 구현하고 이를 matrix 전체에 순차적으로 대입하여 방문처리가 되는 곳의 갯수 counting
• 문제 해결 코드

# 문제 조건 입력
n, m = map(int, input().split())
visited = [[False] * m for _ in range(n)]
# graph 입력
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

dx = [1,-1,0,0]
dy = [0,0,1,-1]

count = 0
# dfs 메소드 정의
def dfs(x, y):
    # 범위 벗어나면 재귀 끝.
    if x < 0 or x >= n or y < 0 or y >= m:
        return False

    # 첫 번째 노드 방문
    if not graph[x][y]:
        graph[x][y] = 1
        # 상,하,좌,우의 노드가 방문 안되어 있으면 dfs 호출하여 방문하기
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    else:
        return False

# N X M 행렬 돌면서 dfs 수행
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            count += 1

print(count)

https://github.com/ybkim-dev/algorithms/blob/master/DFSBFS/음료수%20얼려%20먹기%20with%20dfs.py

💡 문제 2. 미로 탈출

• (1,1)에서 (N,M)의 경로의 최소 칸의 갯수 구하기
• BFS를 사용하여 (간선의 weight 즉, 거리가 1로 동일하므로) 모든 노드의 최단거리 값을 구한다.
  ❗이동시 마다 graph[nx][ny] = graph[x][y] + 1
• 문제 해결 코드

from collections import deque
# 문제 조건 입력
n, m = map(int, input().split())
# graph 입력
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

visited = [[False] * m for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs(x, y):
    global count
    queue = deque()
    queue.append([0,0])
    visited[0][0] = True
    while queue:
        v = queue.popleft()

        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            else:
                if visited[nx][ny] == False and graph[nx][ny] == 1:
                    queue.append([nx, ny])
                    graph[nx][ny] = graph[v[0]][v[1]] + 1
                    visited[nx][ny] = True


bfs(0,0)
print(graph[n-1][m-1])

https://github.com/ybkim-dev/algorithms/blob/master/DFSBFS/미로%20탈출.py