Ch6-DFS/BFS for coding test
- Stack
- Queue
- DFS
- BFS
Q1. Freezing drink
Q2. Escape maze
- Stack
Searching means the process to find data what you want in lots of datas. The problem require to search datas from graph, tree data structure. DFS/BFS is represent searching algorithm and before you to study it, you need to know stack, queue data structure and recursive function. I shortly mention these data structure in Ch3 searching algorithm but we will more study in this chapter.
Data structure means the structure to manage and process the datas. Stack and queue is fundamental idea and it is consist of two essential methods.
- Push : insert data
- Pop : remove data
You need to also consider overflow and under flow. Overflow is the problem when you insert data although the store space is full. Underflow is the problem when you remove data although the store space is empty.
Stack is LiFO ( Last — In — First — Out ) and Metaphorically speaking, it is to store box. when you store box, you put the box from bottom to top. when you remove box, you lifts box from top to bottom. Following figure is simple stack and the total process is ‘push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()’. Let’s look at this process step by step.
step1 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step2 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step3 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step4 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step5 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step6 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step7 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step8 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
This is python code
stack = []
# push(5)-pop(2)-push(3)-push(7)-remove()-push(1)-push(4)-remove()
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]) # reverse order
"""
[5,2,3,1]
[1,3,2,5]
"""
You don’t need to use other library in python. append() method put the data to end of list and pop() method remove the data to end of list.
2. Queue
Queue is FIFO( First — in — First — Out). It is like line-up and the guy who first come go to inside firstly.
Let’s look to process of queue. The total process is same as stack. ‘push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()’.
step1 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step2 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step3 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step4 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step5 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step6 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step7 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
step8 push(5)-push(2)-push(3)-push(7)-pop()-push(1)-push(4)-pop()
This is python code
from collections import deque
# use deque method in collection library
queue = deque()
# push(5)-pop(2)-push(3)-push(7)-remove()-push(1)-push(4)-remove()
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() # reverse order
print(queue) # print reversed order
print(list(queue)) # return list type
"""
deque([3,7,1,4])
deque([4,1,7,3])
[4,1,7,3]
"""
When you implement the queue, i recommend to use ‘deque’ data structure in collection module. ‘deque’ has positive points of stack and queue and it is more fast than list type. Most of coding test allow basic library like collection. If you want to change ‘deque’ object to list type, you can use list() method. I already posted recursive function in Ch2, quick sort. Recursive function can use instead of loop statement. so please check this chapter if you don’t know what is recursive function.
3. DFS
DFS is Depth-First-Search and it search the graph vertically. Before to study DFS, you need to know basic structure of graph. Graph has node and edge. Node is called by vertex in this case. Graph searching is to visit first node and next nodes. If two nodes are connected by edge, it called ‘two nodes are adjacent’.
Graph is expressed in two ways. These two are commonly used in coding test.
- Adjacency matrix : It use 2-dimension array with the connected shape of nodes.
- Adjacency list : It use 2-dimension array with linked list
This is code of adjacency matrix.
INF = 999999999
graph = [
[0,8,5],
[8,0,INF],
[5,INF,0]
]
print(graph)
# [[0, 8, 5], [8, 0, 999999999], [5, 999999999, 0]]This is code of adjacency list
# implement 2-dimension list included 3 rows
graph = [ [] for _ in range(3) ]
# store node information ( node, distance ) to node 0
graph[0].append((1,5))
graph[0].append((2,8))
# store node information ( node, distance ) to node 1
graph[1].append((0,8))
# store node information ( node, distance ) to node 2
graph[2].append((0,5))
print(graph)
# [[(1, 5), (2, 8)], [(0, 8)], [(0, 5)]]What is difference with two method? Adjacency matrix store every relationship of nodes and it use many memory usage when there are many nodes. Adjacency list store the information of linked nodes, it use less memory usage. But Linked list need to check each linked nodes so it is lower than adjacency matrix.
For example, check the node 1 and node 7. You only check the graph[1][7] in adjacency matrix, however, you need to check nodes from node 1 to node7 in the order in adjacency list. So it is efficient when search specific node with every adjacency nodes and adjacency list is efficient in memory perspective. DFS search routes. It search deeply in specific condition and visit the node. Then return the routes and search other routes. The process is like these.
- Input starting node to stack and mark visited position.
- Input smallest adjacent node which is not visited yet to stack and mark visited position. If there are every adjacent node which are already visited , put out the top node form stack.
- Repeat 2 process until finish
Here is graph and we will study how to use DFS searching in this graph.
Get ConfidenceCoding’s stories in your inbox
Join Medium for free to get updates from this writer.
step1. Input starting node ‘1’ to stack and mark visited node.
step2. In the top node ‘1’, there are adjacent nodes which are ‘2’, ‘3’, ‘8’. Input smallest adjacent node ‘2’ to stack and mark visited node.
step3. In the top node ‘2’, there is adjacent node ‘7’ and input the node ‘7’ to stack and mark visited node.
step4. In the top node ‘7’, there are adjacent nodes ‘6’, ‘8' and input the node ‘6’ to stack and mark visited node.
step5. In the top node ‘6’, Every node are already visited. put out node ‘6’ from stack.
step6. In the top node ‘7’, there is adjacent node ‘8’ and input the node ‘8’ to stack and mark visited node.
step7. In the top node ‘8’, Every node are already visited. put out node ‘8’ from stack.
step8. In the top node ‘7’, Every node are already visited. put out node ‘7’ from stack.
step9. In the top node ‘2’, Every node are already visited. put out node ‘2’ from stack.
step10. In the top node ‘1’, there is adjacent node ‘3’ and input the node ‘3’ to stack and mark visited node.
step11. In the top node ‘3’, there are adjacent nodes ‘4’, ‘5’ and input the node ‘4’ to stack and mark visited node.
step12. In the top node ‘4’, there is adjacent node ‘5’ and input the node ‘5’ to stack and mark visited node.
step13. It visited every nodes in graph. Searching order which is the order of inputing stack is like this.
1 => 2 => 7 => 6 => 8 => 3 => 4 => 5
DFS is the algorithm using stack if you use recursive function, the code will be more short. Here is source code.
# Define DFS
def dfs(graph, v, visited):
# mark current node
visited[v] = True
print(v, end=' ')
# visit current node and adjacent node recursively
for i in graph[v]:
if not visited[i]:
dfs(graph, i , visited)
# make information of each nodes to list type
graph = [ [],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# make information of visited node to list type
visited = [False] * 9
dfs(graph,1,visited)
# 1 2 7 6 8 3 4 5
4. BFS
BFS is Breadth-First-Search and it search the graph horizontally. BFS use Queue data structure which is FIFO. When you put adjacent node to queue, it search the nodes horizontally where in near the node ( not deeply ). These are process of BFS algorithm.
- Input starting node to queue and mark visited position
- Put out the node from queue and put the adjacent nodes which is not visited yet to queue. Mark visited adjacent nodes.
- Repeat the process 2 until finish
step1. Input starting node ‘1’ to queue and mark visited node.
step2. Put out node ‘1’ and put the adjacent nodes ‘2’, ‘3’, ‘8’ to queue and mark visited node.
step3. Put out node ‘2’ and put the adjacent nodes ‘7’ to queue and mark visited node.
step4. Put out node ‘3’ and put the adjacent nodes ‘4’, ‘5’ to queue and mark visited node.
step5. Put out node ‘8’ and there is no adjacent node so go to next step
step6. Put out node ‘7’ and put the adjacent nodes ‘6’ to queue and mark visited node.
step7. It visited every nodes in graph. Searching order which is the order of inputing queue is like this.
1 => 2 => 3 => 8 => 7 => 4 => 5 => 6
BFS is simple because it use queue data structure and ‘deque’ library. Additionally, the running time is also fast. Let’s look at the code.
from collections import deque
# Define BFS method
def bfs(graph, start, visited):
# use 'deque' library to implement queue data sturcture
queue = deque([start])
# mark current visited node
visited[start] = True
while queue:
# pirnt one node from queue
v = queue.popleft()
print(v, end=' ')
# input current node and the node which is not visited yet.
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
# make information of each nodes to list type
graph = [ [],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# make information of visited node to list type
visited = [False] * 9
bfs(graph, 1, visited)
# 1 2 3 8 7 4 5 6
Following table is summary of BFS and DFS.
We use the graph for explaining DFS and BFS. You can use this graph when you solve 1-dimension list or 2-dimension list. For example, there is 3 x 3 shape of 2-dimension array.
If you can move to up, down, left and right in this coordinate. You can change this list to graph.
When you solve the search problem in 2-dimension list, it is more easier than thinking about graph for solving question.
Q1. Freeze drink.
There is the ice frame shape of N x M. The empty part is 0 and The divider part is 1. If ice is connected by left, right, up and down, it is considered as one part. Make the program for counting total number of ice cream when given ice frame. For example, ice cream will be made in 4 x 5 ice frame.
Solution
This problem can be solved by DFS and it can be connected by four sides so you can use graph shape. For example, there is 3 x 3 shape of ice frame.
This can be presented like following graph. There are 3 parts after connecting ‘0’ nodes. You can make the program by using DFS. Let’s make the sentence.
This is flow chart
Here is source code for this question.
# Input N, M with space
n, m = map( int, input().split() )
# Input map information of 2-dimension list
graph = []
for i in range(n):
graph.append(list(map(int,input())))
# Visit the node by using DFS after then, visit other connected nodes.
def dfs(x,y):
# Terminate when visiting out of boundary.
if x <= -1 or x >= n or y <= -1 or y >= m;
return False
# If current node isn't visited yet
if graph[x][y] == 0:
# Mark a visit to current node
graph[x][y] = 1
# Call the four side position by using reccursive function
dfs(x - 1 , y)
dfs(x, y - 1)
dfs(x + 1,y)
dfs(x, y + 1)
return True
return False
# Fill 1 to visited node by using DFS
result = 0
for i in range(n):
for j in range(m):
# Implement DFS on current position
if dfs(i,j) == True:
result += 1
print(result)
"""
4 5
00110
00011
11111
00000
3
"""
Q4.Escape maze
Peter be trapped in a maze. Starting position is (1,1) and The exit of maze is (N, M). Peter can move one space by one time and the space where can move is ‘1’, the space where can’t move is ‘0’. Count the minimum space to escape maze.
Solution
BFS is best solution in this problem because it search every node in the graph from nearest step by step. Therefore, You can implement BFS on (1,1) position and input distance value of every nodes. when it visit specific node, plus previous distance of node and ‘1’ to the list. For example, Here is 3 x 3 maze.
step1. Starting position is (1,1)
step2. Visit nearest node and change the value of node to (1,2)
step3. Visit nearest node and plus previous node (1,2) and ‘1’ to current node. It will be (1,3) and repeat these process.
Let’s make the sentence
This is flow chart
Look at the source code
from collections import deque
# Input N,M with space
n,m = map(int, input().split() )
# Input map information of 2-dimension list
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# Define four direction
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# Implement BFS
def bfs(x,y):
# use 'deque' library to implement queue data structure
queue = deque()
queue.append((x,y))
# repeat the process until queue is emptied
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# Terminate when visiting out of boundary.
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# Terminate when visiting the space where can't move
if graph[nx][ny] == 0:
continue
# Mark shortest distance when visiting new node.
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
# return shortest distance to lowest right direction
return graph[n-1][m-1]
print(bfs(0,0))
"""
3 3
110
010
011
5
"""
Summary
Queue : Passing turnel, First car First out
Stack : Stacking box, Last box First out
DFS : Input smallest adjacent node to stack and pop from stack
BFS : Input smallest adjacent node to Queue and pop from queue
