1. 자료구조
자료구조(Data Structure)란 데이터를 표현, 관리, 처리하기 위한 구조를 의미한다.
스택(Stack)은 박스 쌓기에 비유할 수 있다. 후입선출 구조이다. 따라서 기본 리스트에서 append()와 pop()을 이용하면 스택 자료구조와 동일하게 동작한다.
큐(Queue)는 대기줄에 비유할 수 있다. 선입선출 구조이다. 따라서 collections 모듈에 있는 deque 라이브러리를 활용하여 append()와 popleft()를 사용하여 동작할 수 있다 deque 객체를 리스트 자료형으로 변경하고자 한다면 list() 메서드를 이용하면 된다.
2. 재귀함수(Recursive Function)
재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다.
ex)
def recursive_function():
print('재귀함수를 호출합니다.')
recursive_function() #자기 자신을 다시 호출
recursive_function() #함수 실행
이렇게 사용하면 무한히 '재귀함수를 호출합니다' 가 출력되다가 오류가 뜬다. 따라서 재귀함수를 사용할 때는 재귀함수가 언제 끝날지에 대한 종료 조건을 꼭 명시해야 한다.
ex)
def recursive_function(i):
if i == 100: #종료 조건
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1) #자기 자신을 다시 호출
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1) #정의된 함수 실행
3. 탐색 알고리즘
(1) DFS
DFS 알고리즘은 Depth-First-Search, 깊이 우선 탐색을 의미한다.
그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
그래프는 노드(Node)와 간선(Edge)로 표현되며 각 노드를 간선으로 연결되어 있다면 두 노드는 인접하다고 표현한다.
DFS의 동작과정은 아래와 같다.
1) 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.
2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
이때 방문처리는 스택에 한번 삽입된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다.
ex)
def dfs(graph, start, visited):
visited[start] = True #현재 노드 방문처리
print(start, end = '')
for i in graph[start]: #현재 노드와 연결된 다른 노드를 재귀적으로 방문
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]] #각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원)
visited = [False] * 9 #각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원)
dfs(graph, 1, visited) #정의된 함수 호출
(2) BFS
BFS 알고리즘은 Breadth-First-Search, 너비 우선 탐색을 의미한다. 가까운 노드부터 탐색하는 알고리즘이다.
BFS 구현에서는 선입선출 구조의 큐 자료구조를 주로 이용한다.
BFS의 동작과정은 다음과 같다.
1) 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
ex)
from collections import deque
def bfs(graph, start, visited):
queue = deque([start]) #큐 구현을 위해 deque 라이브러리 사용
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
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]] #각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원)
visited = [False] * 9 #각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원)
bfs(graph, 1, visited) #정의된 함수 호출
정리하자면 DFS는 동작원리가 스택을 기초로 하고 구현방법은 재귀함수를 이용한다. BFS는 동작원리가 큐를 기초로 하고 구현방법은 큐 자료구조를 이용한다.
(3) DFS, BFS 어떤 상황에서 사용하는지에 대하여
1) 그래프의 모든 노드를 방문하는 문제 - DFS, BFS
2) 경로의 특징을 저장해둬야 하는 문제 - DFS
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
3) 최단거리 구해야 하는 문제 - BFS
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
4) 검색 대상 그래프가 정말 크다면 DFS를 고려
검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
출처: https://devuna.tistory.com/32 [튜나 개발일기📚]
4. 실전 문제
(1) 음료수 얼려먹기
Q
N X M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시한다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우 붙어 있는 경우에는 서로 연결되어 있는 것으로 간주한다. 이때, 얼음 틀 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.
입력조건
첫째 줄에 얼음 틀의 세로길이 N과 가로길이 M이 주어진다(1<= N,M <= 1000).
둘째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
이때 구멍이 뚫려 있는 부분은 0으로, 그렇지 않은 부분은 1로 주어진다.
출력조건
한번에 만들 수 있는 아이스크림의 개수를 출력한다.
A
DFS를 이용하여 푼다. 현재 위치의 상, 하, 좌, 우 중에서 값이 0이면서 아직 방문하지 않은 지점이 있으면 방문처리 하는 식으로 진행한다.
코드
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 + 1, y)
dfs(x, y - 1)
dfs(x, y + 1)
return True
return False
n, m = map(int, input().split()) #세로길이와 가로길이 입력받기
graph = []
for _ in range(n):
graph.append(list(map(int, input()))) #얼음 틀 모양 입력받기
count = 0
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
count += 1
print(count)
(2) 미로 탈출
Q
동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 밀에는 여러 마리 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 있으며, 한번에 한칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 없는 부분은 1로 표시되어 있다. 동빈이가 탈출하기 위해 움직여야 하는 최소 칸이 개수를 구하시오. 시작 칸과 마지막 칸을 포함하여 모두 계산한다.
입력조건
첫째 줄에 두 정수 N, M(4<=N,M<=200)이 주어진다.
다음 N개의 줄에 각각 M개의 정수가 주어진다. 각각의 수들은 공백 없이 붙어서 주어진다.
시작 칸과 마지막 칸은 항상 1이다.
출력조건
첫째 줄에 최소 이동 칸 개수를 출력한다.
A
최단 거리를 구해야 하므로 bfs를 사용한다.
코드
from collections import deque
def bfs(x, y):
queue = deque(()) #큐 구현을 위해 deque 라이브러리 사용
queue.append([x, y])
while queue: #큐가 빌때까지 반복
x, y = queue.popleft() #큐에서 하나의 원소를 뽑아 출력
for i in range(4): #반복하여 상하좌우 움직임
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m: #미로를 벗어나는 경우는 무시
continue
if graph[nx][ny] == 0: #괴물이 있는 곳은 무시
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1 #한번 움직이면 +1 해주기
queue.append([nx, ny])
return graph[n - 1][m - 1] #최종 위치인 (N, M) 까지의 최단거리 반환
n, m = map(int, input().split()) #미로의 크기 입력
graph = [0] * n #m이 아니라 n이라는거 주의!!
for i in range(n):
graph[i] = list(map(int, input())) #미로의 정보 입력
dx = [-1, 1, 0, 0] #상 하 좌 우 움직임 표현
dy = [0, 0, -1, 1] #상 하 좌 우 움직임 표현
print(bfs(0,0)) #동빈이의 최초 위치 (1,1)을 함수에 넣어서 최소 이동 칸 수 출력
#print(graph) -> [[3, 0, 5, 0, 7, 0], [2, 3, 4, 5, 6, 7], [0, 0, 0, 0, 0, 8], [14, 13, 12, 11, 10, 9], [15, 14, 13, 12, 11, 10]]
