[BOJ] 1405. 미친로봇

문제

미친로봇 (https://www.acmicpc.net/problem/1405)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 횟수가 정해져 있다.
    • DFS, BFS 문제.
  • 확률을 구해야 하므로, DFS, BFS 마지막 스텝에서 지금까지 구한 확률을 모두 더해줘야겠다.
  • 마지막 스텝에서 지금까지의 확률을 가지고있어야 하니, 인자로 지금까지의 확률을 넘겨줘야겠다.
• 알고리즘
  • BFS가 먼저 떠올라 BFS로 구현.
• 코드

# 동서남북 순으로 방향 저장.
dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]

def bfs(x, y):
    q = [(x, y, 1)]
    step = 1
    answer = 0
    visited = {(x, y)}

    while q:
        size = len(q)
        next_visited = set()

        for i in range(size):
            x, y, ratio = q.pop(0)

            for idx, (dx, dy) in enumerate(zip(dxs, dys)):
                nx, ny = x + dx, y + dy
                if (nx, ny) not in visited:

                    # 마지막 움직임인 경우, 모든 확률을 계산하여 더한다.
                    if step >= n:
                        answer += ratio * d_ratio[idx]
                        continue

                    # 아직 움직임이 남아있는 경우, 다음 방문지와 확률을 저장.
                    next_visited.add((nx, ny))
                    q.append((nx, ny, ratio * d_ratio[idx]))

        visited |= next_visited
        step += 1
    return answer


line = list(map(int, input().split()))
n = line[0]
d_ratio = [i/100 for i in line[1:]]

print(bfs(0, 0))

2. 오류

틀렸다고 뜬다. 어디가 문제였을까.
한참 헤매던 중, BOJ Slack 에서, 랭커분이 이렇게 말씀하셨다.

로봇의 움직이는 어떤 경로 그 자체에 한 점이 두 번 나타나면 안 되는 것이지, 다른 경로에서 방문했던 점을 방문하면 안 되는 게 아닙니다.

그렇다… BFS 로 풀면 안된다. DFS 로 풀어야 한다.
한참 뻘짓거리 했다… 후아

3. 다시 제출

• 알고리즘
  • DFS 로 바꾼 것 말고는 전반적인 아이디어는 이전과 동일하다.
  • 처음에만 4방향으로 가고, 이후 3가지 방향으로 뻗어나가므로 (직전 방문한 노드방향으로는 가지않으므로), 시간 복잡도는 O(4 * 3^13) 이다. 이는 400만 정도로, 1억을 넘지않으므로 시간을 초과하지 않고 풀 수 있다.
• 코드

# 동서남북 순으로 방향 저장.
dxs = [0, 0, 1, -1]
dys = [1, -1, 0, 0]

def dfs(x, y, ratio, step):

    if step >= n:
        global answer
        answer += ratio
        return

    visited.add((x,y))

    for idx, (dx, dy) in enumerate(zip(dxs, dys)):
        nx, ny = x + dx, y + dy
        if (nx, ny) not in visited:
            dfs(nx, ny, ratio * d_ratio[idx], step+1)

    visited.remove((x,y))


line = list(map(int, input().split()))
n = line[0]
d_ratio = [i/100 for i in line[1:]]
visited, answer = set(), 0

dfs(0, 0, 1, 0)
print(answer)