DFS

DFS Graph

1) for graph to mark the grid as visited, you can indeed declare 2d visited list. But if it is straightforward graph of 0s and 1s, you can just mark the grid as 0 once you visit it. It saves space.

But this problem is quite hard DFS cuz there is no end conditon. If there is no end condition and we cant return a variable that we have accumulated, we have to use a global count variable.

example:
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2667%EB%B2%88-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0

2) problem with DFS returning None
So you have 2 ways to make DFS return a value
2.1) declare a global variable instead of method parameter

https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2667%EB%B2%88-%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%EB%B6%99%EC%9D%B4%EA%B8%B0

So in here i can just increment the global count variable in dfs function and once dfs finishes I reset the count to 0.

2.2) pass the value as a method parameter

read my revisited explanation its v good

https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-%EC%B4%8C%EC%88%98%EA%B3%84%EC%82%B0

If you just return the value when you meet the recur end condition, at the most recent call stack you get the ride value. But as you pop the call stack, your count variable is overriden, eventually becoming None.

Instead, once once you meet the recursive end condition, use a list and append that answer to the list. like

//recur end condition 
ans.append(count)

3) For backtracking DFS, you have the option to either

taking this example:
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-2529%EB%B2%88-%EB%B6%80%EB%93%B1%ED%98%B8

3.1) change the variable directly, pass that changed variables as parameter and after dfs, undo the changes like

hola+=str(i)
visited[i]=True
dfs(idx+1,hola)
hola=hola[:-1]
visited[i]=False

3.2) OR not change the variable at all in local scope but instead pass the variables as parameter to the dfs backtracking function. So when you backtrack, the variables in the local scope are not changed. Read more in that link

solve(idx+1,hola+str(i))

DFS Graph tips

1) when needing to remove an edge between vertices, maybe use a 2d check_link list like this and after dfs, remember to connect the edge back via making the value True!

check_link[wire[0]][wire[1]] = False
//dfs
check_link[wire[0]][wire[1]] = True

example:
https://velog.io/@whitehousechef/Programmers-%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84-%EB%91%98%EB%A1%9C-%EB%82%98%EB%88%84%EA%B8%B0

2) once you meet the end recursive condition, usually we dont want to keep traversing on. For example if we meet a cycle condition, we dont want to traverse to other nodes but instead we want to return and come back to previous call stack.

Or if we have found a valid path via DFS, we dont want to traverse with the leftover directions in our for loop. Instead we want to return and come back to previous call stack.

example: this 빵집 question is v hard and useful to differentiate return and break. revise
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-3109%EB%B2%88-%EB%B9%B5%EC%A7%91