https://www.acmicpc.net/problem/2644
initial
wrong code:
def dfs(start,end,count):
if start==end:
return count
visited[start]=True
count +=1
for node in graph[start]:
if not visited[node]:
dfs(node,end,count)
return count
count = dfs(start,end,0)The dfs returned None and that is the biggest paradox I have with DFS recursion with Python. Even when the condition is met and I want to break out of the whole DFS recursion by returning that count answer, it only breaks out in the inner DFS and the other DFS overrides this count value.
There is a simple solution for this. Create a list and append that count answer that we are looking for. It saves the answer in our list that can be extracted later.
[revisited jan 9th 24] or i think you can do count += dfs() and then return count at the end [revisited 13th jan] i tired and cant
also the end recursive condition should have a return? either to make it more eff. or if you traverse beyond that, it will cause error. Here luckily it didnt cause error but to make it more eff (my below sol is 72ms but most py sol are 40ms), add return
btw besides appending to a list, you can also declare 1d distance list of size n and updating the distance to each node (like dijkstra) like this
dist = [-1] * (n + 1)
def dfs(curr, end, depth):
if curr == end:
return
for dst in graph[curr]:
if dist[dst] == -1:
dist[dst] = depth + 1
dfs(dst, end, depth + 1)solution
My correct code:
from collections import defaultdict, deque
import sys
sys.setrecursionlimit(300000)
N = int(input())
start,end = map(int, input().split())
M = int(input())
graph = defaultdict(list)
ans =[]
####
# 어떤 노드들이 연결되어 있는지 graph라는 2차원 배열에 저장
for _ in range(M):
x, y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
visited = [False for _ in range(N+1)]
# global count
# count = 0
def dfs(start,end,count):
if start==end:
ans.append(count)
visited[start]=True
count +=1
for node in graph[start]:
if not visited[node]:
dfs(node,end,count)
dfs(start,end,0)
if len(ans)==0:
print(-1)
else:
print(ans[0])revisited may 17th
Its rather a simple question. Once you see the end condition of reaching the final target node, i print the depth which has been incremented via method parameter and exit. Even after all the dfs search and we havent exited out of the program yet, we print -1.
But gemini refactored my code to a better one without using exit(). Lets think of the base case like the case when we have reached the deepest node in our dfs. The base case is that that deepest node should be our final destination node so we return depth. All its neighbouring nodes would have been visited. But if it is not the target destination node, we need to return -1.
my solution with exit()
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)
def dfs(node, depth):
if node == b:
print(depth)
exit(0)
for child in graph[node]:
if not visited[child]:
visited[child] = True
dfs(child, depth + 1)
n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = defaultdict(list)
for _ in range(m):
c, d = map(int, input().split())
graph[c].append(d)
graph[d].append(c)
visited = [False] * (n + 1)
visited[a] = True
dfs(a, 0)
print(-1)gemini's refactored sol without exit()
If you look, once call stack is popped and result is returned, there is a if statement that prevents overriding of value. If there indeed is a value, it returns result again.
n = int(input())
a, b = map(int, input().split())
m = int(input())
# Create an undirected graph using defaultdict(list)
graph = defaultdict(list)
for _ in range(m):
c, d = map(int, input().split())
graph[c].append(d)
graph[d].append(c)
# Initialize visited array with False values for all nodes
visited = [False] * (n + 1)
def dfs(node, depth):
"""Performs a Depth-First Search (DFS) on the graph to find the shortest path
between nodes a and b.
Args:
node (int): The current node being explored in the DFS.
depth (int): The current depth level in the search.
Returns:
int: The depth of the target node b if found, -1 otherwise.
"""
# Mark the current node as visited
visited[node] = True
# Base case: If the target node is found, return the current depth
if node == b:
return depth
# Explore unvisited child nodes
for child in graph[node]:
if not visited[child]:
# Recursively search for the target node through the child
result = dfs(child, depth + 1)
# If the target node is found in a child subtree, return the depth
if result != -1:
return result
# If the target node is not found in any child subtree, return -1
return -1
# Start the DFS from node a with depth 0
shortest_path_depth = dfs(a, 0)
# Print the shortest path length if found, otherwise -1
print(shortest_path_depth if shortest_path_depth != -1 else -1)
