백준 1405: 미친 로봇

관련 링크 : https://www.acmicpc.net/problem/1405

백준 1405 : 미친 로봇

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

입력

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

확률의 단위는 %이다.

2 25 25 25 25

출력

첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

0.75

풀이

처음에 문제를 잘못 이해해 단순한 경로는 이전에 도달한 곳을 다시 도달하지 않는 경로인데, 원점으로 다시 돌아오는 경로라고 생각했다. 그래서 가능한 모든 경로를 나열한 후 그 경로가 원점에 도달하는지 하지 않는지 확인했는데, 문제를 다시 살펴보니 그게 아니어서 새로 풀었다.

물론 모든 경우의 수를 만들면 메모리 초과가 뜬다. 처음엔 문자열로 경우의 수를 만들다가, 원점으로 돌아오는 경우면 동과 서, 남과 북 각각의 개수가 같은 경우이므로 동과 남을 1, 서와 북을 -1로 하여 좌표 형식으로 만드니 메모리 초과는 뜨지 않았는데 시간 초과는 뜨더라.

DFS를 이용해 풀었다.

n, east, west, south, north = map(int, input().strip().split()) #입력 처리
move_probs = [east/100, west/100, south/100, north/100]
dx = [1, -1, 0, 0] #동, 서
dy = [0, 0, -1, 1] #남, 북

coords = [] #이전에 방문한 좌표들을 기록
result = [] #단순하지 않은 경로들의 확률을 저장
def dfs(n, cur=[0, 0], prob=1):
    if cur not in coords: #현재 경로가 단순하면 수행
        if n!=0:
            for x, y, move_prob in zip(dx, dy, move_probs):
                coords.append(cur)
                nxt = [cur[0]+x, cur[1]+y]
                nxt_prob = prob * move_prob
                dfs(n-1, nxt, nxt_prob)
                coords.pop()
    else: #현재 경로가 단순하지 않으면 수행
        result.append(prob)

dfs(n)
print(1-sum(result)) #단순한 경로의 확률 계산

그런데, 계속 시간 초과가 뜨더라. 질문들을 살펴보니 방문 전에 단순한지 확인하는 것과 방문 후에 확인하는 것이 시간 복잡도 차이가 난다고 한다. 그래서 방문 전에 확인하는 것으로 코드를 수정했다.

방문 전에 확인하면 이전에 이동한 방향의 반대 방향은 당연히 복잡한 경로이므로 방문하지 않아도 제거되지만, 방문 후에 확인하면 당연히 아닌 것을 한번 더 방문하게 된다. 따라서 방문 전은 $4\times 3^{n-1}$인 반면, 방문 후는 $4^n$의 시간 복잡도를 가진다고 한다. 입력으로 14 25 25 25 25를 준 경우 함수의 호출 횟수를 비교해보면, 방문 전은 3770841, 방문 후는 5585589로 확연하게 차이가 나는 것을 볼 수 있었다.

n, east, west, south, north = map(int, input().strip().split())
move_probs = [east/100, west/100, south/100, north/100]
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

coords = []
result = 0
def dfs(n, cur=[0, 0], prob=1):
    global result #굳이 List를 써야하나 싶어서 수정
    if n!=0:
        for x, y, move_prob in zip(dx, dy, move_probs):              
            nxt = [cur[0]+x, cur[1]+y]
            if nxt not in coords: #다음 경로가 단순하면 수행
                coords.append(cur)
                dfs(n-1, nxt, prob * move_prob)
                coords.pop()
    else: #단순한 경로만 탐색하므로, 모든 경우가 단순한 경로
        result += prob

dfs(n)
print(result)