Before
DFS, BFS에 대한 개념을 배우기에 앞서 '스택(Stack)', '큐(Queue)', '재귀함수(Recursive Function)'에 대한 개념을 알고 진행하면 이해가 쉬울 것입니다.
스택(Stack)
한국말로는 "쌓다"라는 의미로 해석되며 선입후출(FILO : First In Last Out) or 후입선출(LIFO : Last In First Out) 구조로 이루어져 있습니다.
구현하기 위해 필요한 Python 메소드
stack = list()
# list = [뒤 <---------> 앞]
stack.append() # 리스트의 가장 뒤쪽에서 데이터를 삽입
stack.pop() # 리스트의 가장 앞쪽에서 데이터를 꺼낸다큐(Queue)
책에서는 "대기 줄"이라는 좋은 비유로 선입선출(FIFO : First In First Out) 구조로 이루어져 있습니다.
구현하기 위해 필요한 Python 메소드( * Collections 모듈이라는 Python 라이브러리 이용)
from collections import deque
queue = deque()
# list = [뒤 <---------> 앞]
queue.append() # 리스트(Deque형)의 가장 뒤쪽에서 데이터를 삽입
queue.popleft() # 리스트(Deque형)의 가장 뒤쪽에서 데이터를 꺼낸다
queue.reverse() # 리스트(Deque형)을 역순으로 바꾸기 재귀 함수(Recursive Function)
"자기(자신)"을 다시 호출하는 함수이다. 주의해야 할 사항은 무한적으로 호출하기 때문에, 특정한 조건을 만족하게 만들어 멈추게 하는 조건 생성에 대해서 한 번씩 고려해봐야 합니다.
재귀 함수는 수학의 '점화식'을 그대로 적용했기에 '점화식' 개념에 대해서 알고 넘어가면 좋을 것 같습니다.
def recursive_function():
print("재귀 함수를 호출합니다.")
recursive_function()
recursive_function()DFS
Depth First Search으로 '깊이 우선 탐색'이라는 의미를 가지고 있습니다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 여기서 말하는 그래프(Graph)는 여러 개의 노드(Node)들이 간선(Edge)으로 연결되어 있는 집합체라고 말할 수 있습니다.
👉 DFS의 동작원리는 "스택(Stack)"이며, 구현 방법은 "재귀 함수"를 이용하는 것이 포인트!def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
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]
]
visited = [False] * 9
dfs(graph, 1, visited)BFS
Breadth First Search으로 '너비 우선 탐색'이라는 의미를 가지고 있습니다. DFS의 반대로, 가장 가까운 노드부터 탐색합니다. 보통 DFS보다 BFS 구현이 조금 더 빠르게 동작한다고 합니다.
👉 BFS의 동작원리 및 구현방법은 "큐(Queue)"을 이용하는 것이 포인트!from collections import deque
def bfs(graph, start, visited):
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
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)문제 및 풀이
문제 1. 음료수 얼려 먹기
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
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):
if(dfs(i, j) == True):
result += 1
print(result)const solution = (n, m, arr) => {
let answer = 0;
let dx = [0, 0, -1, 1];
let dy = [-1, 1, 0, 0]
const DFS = (x, y) => {
arr[x][y] = 1;
for (let i = 0; i < dx.length; i++) {
let nx = x + dx[i];
let ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] === 0) {
arr[nx][ny] = 1;
DFS(nx, ny);
}
}
}
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr[i].length; j++) {
if (arr[i][j] === 0) {
DFS(i, j);
answer++;
}
}
}
return answer;
}
let arr = [
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0]
];
console.log(solution(4, 5, arr));Algorithm/dfs_2.js at main · sanghyuk-2i/Algorithm
문제 2. 미로 탈출
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = 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
queue.append((nx, ny))
return graph[n - 1][m - 1]
print(bfs(0, 0))const solution = (n, m, arr) => {
let answer = 0;
let queue = [];
let dx = [0, 0, -1, 1];
let dy = [-1, 1, 0, 0];
const BFS = (x, y) => {
queue.push([x, y]);
while (queue.length > 0) {
let check = queue.shift();
for (let i = 0; i < dx.length; i++) {
let nx = check[0] + dx[i];
let ny = check[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] === 1) {
arr[nx][ny] = arr[check[0]][check[1]] + 1;
queue.push([nx, ny]);
}
}
}
}
BFS(0, 0);
return arr[n - 1][m - 1];
}
let arr = [
[1, 0, 1, 0, 1, 0],
[1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1]
];
console.log(solution(5, 6, arr));Algorithm/bfs_2.js at main · sanghyuk-2i/Algorithm
참고 자료 및 출저
사진 출저
그 외 참고 자료
