1405. 미친 로봇 (Python)

1405번: 미친 로봇

 

풀이

 백트래킹을 활용해서 해결할 수 있는 문제다. 먼저 30 * 30 사이즈의 방문 체크 리스트를 만들고 로봇이 해당 리스트의 가운데에 위치해 있다고 가정한다. 그 후 동서남북으로 한 번씩 체크하여 방문하지 않은 위치에 해당하면 로봇을 해당 위치로 이동시키고 다시 함수를 호출한다. 

 동서남북으로 진행해 나갈때마다 해당 방향으로 이동할 확률을 곱해 나가 N번 이동을 마쳤을 때 구한 확률을 모두 더해준다. 만약 이동중에 이미 방문한 위치에 해당할 경우에는 함수를 호출하지 않는 방식으로 가지치기를 해주면 된다.

 

코드

# n: 로봇이 취한 행동 횟수, x&y: 현재 로봇의 위치, percentage: 현재까지 이동한 경로의 확률
def pathFind(n, x, y, percentage):
    if n == N:  # 로봇이 총 N번의 행동을 취했다면 단순 이동 경로에 해당
        global simple
        simple += percentage  # 계산한 확률을 더해준다
        return

    # 각 이동 확률이 0이 아닐 경우에
    if east != 0:
        if not visited[x][y+1]:  # 해당 방향으로 이동했을 때, 방문하지 않은 위치일 경우에만
            visited[x][y+1] = True  # 방문 체크를 해주고
            pathFind(n+1, x, y+1, percentage*(east/100))  # 함수 재귀 호출
            visited[x][y+1] = False  # 다시 해당 위치의 방문 체크를 해제해준다

    if west != 0:
        if not visited[x][y-1]:
            visited[x][y-1] = True
            pathFind(n+1, x, y-1, percentage*(west/100))
            visited[x][y-1] = False

    if south != 0:
        if not visited[x+1][y]:
            visited[x+1][y] = True
            pathFind(n+1, x+1, y, percentage*(south/100))
            visited[x+1][y] = False

    if north != 0:
        if not visited[x-1][y]:
            visited[x-1][y] = True
            pathFind(n+1, x-1, y, percentage*(north/100))
            visited[x-1][y] = False


if __name__ == '__main__':
    # 로봇의 행동 횟수, 동쪽 이동 확률, 서쪽 이동 확률, 남쪽 이동 확률, 북쪽 이동 확률
    N, east, west, south, north = list(map(int, input().split()))
    visited = [[False for _ in range(30)] for _ in range(30)]  # 방문 체크 리스트
    visited[15][15] = True  # 현재 로봇은 [15][15]에 있다고 가정한다.

    simple = 0.0  # 단순 이동 경로일 확률
    pathFind(0, 15, 15, 1)

    print(simple)