[BOJ] 1405. 미친 로봇(Python) / DFS

www.acmicpc.net/problem/1405

1405번: 미친 로봇

생각보다 시간이 좀 걸렸다.. 문제 이해하는데 난독증이 심해 한참 걸렸다ㅠㅠ

문제만 잘 이해하고 나니 어렵지 않게 바로 술술 풀렸던 문제다.

• 사용 알고리즘 : DFS
• 인풋 받으면서 사용하기 편하도록 동서남북 방향별 percentage는 100으로 각각 나누어 리스트로 저장했다.
• 미리 한 방향으로만 갔을 때 상하좌우에 대해 최대 N만큼 갈 수 있으므로 현 위치를 중간으로 봤을 때 현 위치 포함해 N*2 + 1 크기의 check 배열을 만들어뒀다.
• dfs 함수에는 depth, 현 위치 (N, N), percentage 이렇게 4개의 인자로 돌렸다.
• dfs 함수 안에서 depth가 N에 다다르면 확률을 result에 더해준 후 리턴한다.
• 쉽게 생각하면 순열인데, 방문 표시를 하면서 이동하는데  방문표시 된 곳은 못 간다. 그 경우를 제외하고 모든 경우에 대해 확률을 더해준다고 보면 된다.
• 4방향에 대해 방문 표시하면서 다음 위치 (nr, nc)를 인자로 넘기며 재귀로 dfs를 수행한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

dr = (0, 0, 1, -1)
dc = (1, -1, 0, 0)

def dfs(depth, r, c, percentage):
    global result
    if depth == N:
        result += percentage
        return
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if check[nr][nc]:
            continue
        check[nr][nc] = 1
        dfs(depth+1, nr, nc, percentage*dirInfo[i])
        check[nr][nc] = 0

# main
N, east, west, south, north = map(int, input().split())
dirInfo = [east/100, west/100, south/100, north/100]

result = 0
check = [[0] * (2*N+1) for _ in range(2*N+1)]
check[N][N] = 1
dfs(0, N, N, 1)
print(result)

---

• 시간 : 544ms / 메모리 : 127308kb
• 고찰 : 간단한 DFS 문제였다. 구상은 금방 했는데, 왜 푸는데 한 시간이나 걸렸는지 모르겠다ㅠㅠ 문제를 정확히 이해하고 코드로 옮기자!