Marathon

DFS

How to Solve Graph Problems

• My initial approach didn’t use a graph structure, which led to overly complex and unnecessary data structures (like in marathon.cpp) and eventually hit a dead end.
• When solving a graph problem, build the graph first.

int V, E, u, v, d;
int edge[27], val[27][27], node[27][27], visit[27];
int ans[27],  course[27];
int a_cnt, c_cnt = 0, D, min_d = 21, goal_d = 42;
int cur_max = 0;

• Start by setting up the graph-related variables like above.

int	main(void){
	my_input();
	DFS(0, 0);
	choose_optimal();
}

• Once the input is received, begin DFS immediately based on the values provided.

Inside the DFS

• If the current vertex is 'a', stop the process — that means we’ve reached the destination → check if the current vertex is 'a' using an if statement.
  • If we’ve arrived, we need to record the path we’ve taken so far.
• If the vertex is not 'a', check whether we’ve visited it before.
  • If it hasn’t been visited, go deeper into the recursion (i.e., move to a deeper level of DFS).

Difficult Parts

• One of the hardest parts is figuring out how to handle the visited matrix when arriving at 'a'.
• I keep getting stuck because of how to reset or manage the visited array correctly.

DFS Thought Process

• Define a clear termination condition — when should the recursion stop?
• Use a loop to go through all the next possible connected vertices from the current node, and recursively DFS each of them.
• After returning from DFS, remove the selected node from the visited array and the path array to backtrack properly.

Current Problem

• For some reason, when I set the destination to 'a', the number of valid paths that meet the problem’s constraints is zero…
• I’m not sure why this is happening — need to figure out how to fix it.