문제

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

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

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

입력

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

확률의 단위는 %이다.

출력

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

풀이

로봇이 N번 만큼의 이동을 하는데 방문했던 곳을 다시 간다면 안되는 문제이다.
즉 방문 안한 곳만 N번을 이동하는 확률의 합을 구하면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

C,E,W,N,S = map(int,input().split()) # count, 동서남북 순
graph = [[0]*30 for _ in range(30)]  # 임의의 좌표를 만들어 준다
graph[15][15]=1                      # 중간지점이 내가 시작할 좌표
result =0                            # 최종 확률

def dfs(y,x,per,count):             # y좌표 , x좌표, 현재 확률, 남은차례
    global result
    dy = [0,0,1,-1]                 # 동서남북 순
    dx = [1,-1,0,0]

    if count==0:                    # 남은차례가 없다면
        result+= per                # 결과 넣고 끝내기
        return

    for i in range(4):              # 네방향 순회하면서
        ny = y+dy[i]
        nx = x+dx[i]
        if graph[ny][nx] == 0:      # 그 자리가 방문 안한 자리라면
            if i==0:                # j = 동서남북으로 갈 확률
                j = E/100
            elif i==1:
                j = W/100
            elif i==2:
                j = N/100
            elif i==3:
                j = S/100

            if j != 0:                   # j가 0이 아니라면
                graph[ny][nx] = 1        # 방문 해주고
                dfs(ny,nx,per*j,count-1) # dfs()
                graph[ny][nx]=0          # dfs가 끝나면 다시 방문 취소
dfs(15,15,1,C)
print(result)

현상 & 수정
처음에는 조합을 이용해서 3 50 50 0 0 이라면 E E E W W W 의 리스트를 세개의 조합을 이용해 풀려고 했는데, N = 14가 되는 순간 메모리가 폭발하게 된다.
그래서 간단한 dfs를 이용해 다시 풀게 되었다.