Gihyun Kim

Author: Gihyun Kim

Date: April 11th, 2024

Topic: DFS Algorithm and its use

What is DFS?
DFS, or Depth First Search, is a searching algorithm that is commonly used to traverse a tree or graph data structure. It starts at a specific (randomly chosen) node and goes through the selected path as much as it can along each branch present in the tree. After it has fully explored one node, it starts the process of backtracking to explore other nodes.
The main idea behind this searching method is to fully explore all the nodes and branches before backtracking and going to another one. As of now, I have only learned the recursive method of the DFS algorithm and it has enabled me to solve a more diverse array of problems but I hope to learn different ways of implementing DFS in coding as well as possible learning different algorithms.

Benefits:
Here are some benefits to the DFS algorithm:
1. Memory Efficiency: The DFS algorithm, especially when compared to BFS, is very memory efficient, meaning that it does not take up too much space in the computer’s memory which is beneficial for when solving problems in USACO or in other situations where the code is in a “stress test.”
2. Deep Searching: The DFS enables the programmer to go more in-depth into each node which allows them to fully traverse through each node/branch of the tree as it tends to fully explore each part of the data structure which can be useful when finding all possible routes or a repeating data structure.
3. Maze-Solving: DFS can be very useful in solving mazes or even sudoku problems as it uses backtracking to explore all possibilities which allows for the time-effective and memory-effective maze solving.
4. Pathfinding: Although DFS doesn’t guarantee the shortest path, it can be useful in certain scenarios, such as finding any path between two nodes or backtracking to find all possible paths.

Uses:
This is a problem that I have solved using the DFS algorithm which is combining difference strands of DNA into one and finding the most effective, shortest, way to do so.

https://www.jungol.co.kr/problem/2217?cursor=eyJwcm9ibGVtc2V0IjoiOCIsImZpZWxkIjozLCJpZHgiOjd9
This is the link to the question and because it is fully in korean I will translate the important parts below

Question:
Find the shortest way to connect the DNA strands that are given as the input values and output the length of the DNA strand. The guidelines to follow is to only combine the matching parts of the DNA, so, for example, if there were two DNA strands of GATTA and TACA, it could be combined to GATTACA as the TA part is the same for both sides.

Code:
Here is the code that I wrote to solve this problem. It uses the DFS algorithm and was deemed correct by the tester/compiler.