[백준] 1189번: 컴백홈

https://www.acmicpc.net/problem/1189

initial

easy backtracking question. i always find board questions easier than list

but my initial solution kept printing 0 so I wrote this. be careful
https://velog.io/@whitehousechef/DFS-outputting-0

solution

n, m, a = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(input().rstrip()))

ans = 0
moves = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = [[False for _ in range(m)] for _ in range(n)]

def dfs(x, y, count):
    global ans
    if x == 0 and y == m - 1:
        if count == a:
            ans += 1
        return
    if count>a:
        return

    for move in moves:
        next_x = move[0] + x
        next_y = move[1] + y
        if 0 <= next_x < n and 0 <= next_y < m:
            if not visited[next_x][next_y] and graph[next_x][next_y] != 'T':
                visited[next_x][next_y] = True
                count += 1
                dfs(next_x, next_y, count)
                visited[next_x][next_y] = False
                count -= 1
visited[n - 1][0]=True
dfs(n - 1, 0, 1)
print(ans)

better solution

you dont need a separate 2d visited list. marking visited as 'T' will do and for backtracking, redeclare it back to ' '.

revisited jan 16th 2024

I just tried thinking of the diff between dfs and dfs backtracking. If we just do dfs, once we find 1 valid solution (which meets the recur end condition), we return all the way, ignoring the call stacks. That is why we normally do dfs for each grid like

for i in range(x):
	for j in range(y):
    	dfs()

But for backtracking, if we undo the changes that we made as we traverse through the board, the previous call stacks can traverse other possible paths.

That is why we can calc multiple paths from just 1 starting point instead of normal dfs that is conducted in a double for loop.

BTW nice trick to end the backtracking early if count exceeds the given a.

complexity

The time complexity of your code is exponential, specifically O(4^(n*m)), where "n" and "m" are the dimensions of the grid. This is because, in the worst case, your depth-first search (DFS) explores all possible paths through the grid.

The space complexity is O(n*m) due to the visited array and the function call stack used for recursion.

Your code will work correctly, but it can become very slow for larger grids due to its exponential time complexity. Consider optimizing it if you need to handle larger input sizes.