I implemented both DFS and BFS approaches for the problem, and the BFS approach is working fine but DFS approach is giving wrong answer for subtask #2. All the submissions I saw on DFS failed subtask #2.
Can anyone please explain to me why it is failing?
Thanks in advance!
DFS does not find the shortest path, which is required in the problem.
I’ve seen many posts stating that DFS does not always find the shortest path. But, I don’t quite understand the intuition behind it. In my implementation, I’m taking the shortest of all the possible paths from the start recursively. Can you please help me understand why my approach is flawed?
DFS will not always find the shortest path. Below example might help you understand the problem with DFS approach:
1
8 8
01000010
00100000
00010000
00001000
00000101
00001000
00000100
00000000
Just draw the above graph in paper to visualize the graph. DFS approach will give answer as 5. But the correct answer is 4.
The reason is that DFS can choose the node in any arbitrary manner. If it chooses 0->1 first, then it gives wrong answer.
Yes,
In BFS, you can never traverse nodes at distance d+1 before traversing all the nodes at distance d from the root (like level order).
In DFS, on the other hand, you just go deeper and deeper and deeper until you find a dead end. You don’t traverse all the nodes of distance ‘d+1’ together.
