DFS / BFS (깊이우선탐색 / 너비우선탐색)

 

스택 (LIFO)

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)          # 최하단 원소부터 출력
print(stack[::-1])    # 최상단 원소부터 출력

- 별도의 라이브러리 없이 리스트의 append(), pop() 메서드 이용

 

 

큐 (FIFO)

from collections import deque

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

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)        # 나중에 들어온 원소부터 출력

- collections 모듈에서 제공하는 deque 자료구조를 활용 (스택+큐의 장점)

- 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리보다 간단함.

- list() 메서드를 이용하면 deque 객체를 리스트 자료형으로 변경할 수 있음.

 

 

재귀 함수

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

- 종료 조건 명시

- 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용

- 따라서 스택 자료구조를 활용해야 하는 많은 알고리즘은 재귀 함수를 이용해서 간단하게 구현 가능. ex) DFS

##### 재귀 함수 예시 - 팩토리얼 #####

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:  # 종료 조건
        return 1
    return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))

 

 

그래프 표현

- 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

- 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

인접행렬 - 메모리 낭비. but 탐색 빠름 / 인접리스트 - 메모리 효율적. but 탐색 느림

# 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

INF = 99999999999 # 무한의 비용 선언 (초기화)

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

# 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

 

 

DFS (깊이 우선 탐색)

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

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

- 동작 과정

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

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

        방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

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

- 실제로는 스택을 쓰지 않아도 되며, 탐색 시간 O(N)

# 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 (너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- 큐 자료구조를 이용

- 동작 과정

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

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

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

- O(N). 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편.

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. 음료수 얼려 먹기

n, m = map(int, input().split())
list = [[] for _ in range(n)]

for i in range(n):
    data = input()
    for j in range(m):
        list[i].append(int(data[j]))

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= m:  # x, y 좌표가 맵을 벗어나면
        return False
    if list[x][y] == 0: # 얼음 틀에 구멍이 뚫려 있는 부분
        list[x][y] = 1 # 방문 체크
        # 상, 하, 좌, 우 체크
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
        return True
    else:
        return False

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i, j) == True:
            result += 1

print(result)

- DFS로 풀 수 있다.

    1) 특정한 지점의 주변 상, 하, 좌, 우 살펴본 뒤에

        주변 지점 중 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문

    2) 방문한 지점에서 다시 상, 하, 좌, 우 살피면서 방문 다시 진행

 

 

예제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))

- BFS로 풀 수 있다.

이런 원리로 작동함

 

역시 그래프 탐색 문제는 어렵다

나랑 안 맞 아