[백준] 1405번: 미띤 로봇

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

initial

lst = list(map(int, input().split()))
visited = [[False for _ in range(50)] for _ in range(50)]
n = lst[0]
prob=[]
total = 1
for i in range(1,5):
    if lst[i]!=0:
        total *=n
    prob.append(lst[i]/100)
print(prob)
print(total)
ans = 0

moves = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visited[25][25] = True

def dfs(row, col, count, p, check):
    global ans, n, prob
    if check == n:
        if count < n:
            ans += 1 
        return

    for i in range(4):
        if prob[i] != 0:
            next_row, next_col = moves[i][0] + row, moves[i][1] + col
            if not visited[next_row][next_col]:
                visited[next_row][next_col] = True
                dfs(next_row, next_col, count + 1, p * prob[i], check + 1)
                visited[next_row][next_col] = False
            else:
                dfs(next_row, next_col, count, p * prob[i], check + 1)
                visited[next_row][next_col] = False

dfs(25, 25, 0, 1, 0)

print(ans)

solution

1) we shouldnt just add the number of possibilities by incrementing ans by 1 when we see a valid path. This is cuz it will be tricky to find the total number of valid paths. Instead, we can just add the probability when we see a valid path

wrong:

    if check == n:
        if count < n:
            ans += 1 
        return

correct:

    if check == n:
        if count == n:
            ans += p
        return

2) Actually we dont even need to backtrack once we see an already visited grid.

wrong:

            else:
                dfs(next_row, next_col, count, p * prob[i], check + 1)
                visited[next_row][next_col] = False

what this does is we mark the original start point (25,25) as unvisited when we backtrack. Instead, what we should do is continue on to next iter ith move once we see a visited grid.

3) i declared 50x50 grid according to n being up to 14 max. But whilst you can do that, you can actually declare visited as a simple list of start point (0,0) like visited = [(0, 0)]

Then, we dont need to care about going (-1,0) and beyond 2x2 grid cuz visited is not declared as 2x2 grid in the first place and is just a simple list that can accept negative value.

my solution

lst = list(map(int, input().split()))
visited = [[False for _ in range(50)] for _ in range(50)]
n = lst[0]
prob=[]
total = 1
for i in range(1,5):
    if lst[i]!=0:
        total *=n
    prob.append(lst[i]/100)
ans = 0

moves = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visited[25][25] = True

def dfs(row, col, count, p, check):
    global ans, n, prob
    if check == n:
        if count == n:
            ans += p
        return

    for i in range(4):
        next_row, next_col = moves[i][0] + row, moves[i][1] + col
        if not visited[next_row][next_col]:
            visited[next_row][next_col] = True
            dfs(next_row, next_col, count + 1, p * prob[i], check + 1)
            visited[next_row][next_col] = False
        else:
            continue
            # dfs(next_row, next_col, count, p * prob[i], check + 1)
            # visited[next_row][next_col] = False

dfs(25,25,0,1,0)
print(ans)

by using a list for visited

d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 4방향 탐색

def dfs(r, c, visited, total):
    global answer
    if len(visited) == N+1:
        answer += total
        return
    for idx in range(4):
        nr = r + d[idx][0]
        nc = c + d[idx][1]
        if (nr, nc) not in visited:
            visited.append((nr, nc))
            dfs(nr, nc, visited, total*probability[idx])
            visited.pop()

N, ep, wp, sp, np = map(int, input().split())
probability = [ep, wp, sp, np]
answer = 0

dfs(0, 0, [(0, 0)], 1)
print(answer * (0.01 ** N))

complexity

space is 5050 so around (2n)2?
time is 4n?

time is 4*n and for space, grid is o(1) so space will be dominated by the recursion stack, which is equal to the number of steps (n)