[Gold IV] 미친 로봇 - 1405

문제 링크

성능 요약

메모리: 37120 KB, 시간: 1336 ms

분류

수학, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 깊이 우선 탐색, 백트래킹, 확률론

문제 설명

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

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

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

입력

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

확률의 단위는 %이다.

출력

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

---

문제 풀이

문제 분석

문제는 미친 로봇이 N번 움직일 때, 단순한 경로(이미 방문한 곳을 다시 방문하지 않는 경로)로 이동할 확률을 구하는 것입니다. 입력으로는 N과 동, 서, 남, 북으로 이동할 확률이 주어집니다. 출력은 단순한 경로로 이동할 확률입니다.

접근 방법

이 문제는 깊이 우선 탐색(DFS)과 백트래킹을 사용하여 해결할 수 있습니다. 로봇이 이동할 수 있는 모든 경로를 탐색하면서, 이미 방문한 곳을 다시 방문하는 경우를 제외하고, N번 이동했을 때의 확률을 계산하여 더합니다. 백트래킹을 사용하여 탐색 후 방문 기록을 되돌려 다른 경로를 탐색할 수 있도록 합니다.

구현 설명

1. 입력 처리 및 초기화

• 입력을 받아 N과 각 방향으로 이동할 확률을 저장합니다. 각 확률을 100으로 나누어 0과 1사이의 값으로 변환합니다.
• visited 리스트를 생성하여 로봇이 방문한 위치를 기록합니다. 2차원 배열로 구현하며, 로봇이 움직일 수 있는 범위를 고려하여 크기를 설정합니다. (30x30)
• 로봇의 시작 위치를 (15, 15)로 설정하고, visited 리스트에 방문했음을 표시합니다. 시작 위치를 중앙으로 잡는 이유는 로봇이 N번 이동할 때 음수 좌표로 벗어나는 것을 방지하기 위함입니다.

2. DFS 함수 구현

• DFS(level, prob, visited, x, y) 함수는 현재 레벨(이동 횟수), 현재까지의 확률, 방문 기록, 현재 로봇의 좌표를 인자로 받습니다.
• level이 l (총 이동 횟수 N)과 같으면, 현재까지의 확률 prob를 반환합니다.
• 로봇이 이동할 수 있는 4가지 방향(동, 서, 남, 북)에 대해 반복합니다.
  • 각 방향으로 이동했을 때의 새로운 좌표 (nx, ny)를 계산합니다.
  • 새로운 좌표가 이미 방문한 곳인지 확인합니다. 만약 방문했다면, 해당 경로는 단순하지 않으므로 건너뜁니다.
  • 만약 방문하지 않았다면, visited 리스트에 방문했음을 표시하고, DFS 함수를 재귀적으로 호출합니다. 이때 level을 1 증가시키고, prob에 해당 방향으로 이동할 확률을 곱합니다.
  • 재귀 호출이 끝난 후, visited 리스트에서 방문 기록을 제거합니다 (백트래킹). 이는 다른 경로를 탐색할 때 영향을 주지 않도록 하기 위함입니다.
• 모든 방향에 대한 탐색이 끝나면, 계산된 모든 확률의 합을 반환합니다.

3. 초기 DFS 호출 및 결과 출력

• 로봇이 처음 움직일 수 있는 4가지 방향에 대해 DFS 함수를 호출합니다. 각 방향으로 이동할 때, 시작 위치에서 해당 방향으로 이동한 후 DFS 함수를 호출합니다.
• 각 DFS 호출의 결과를 더하여 최종 확률을 계산합니다.
• 계산된 최종 확률을 출력합니다.

⏱복잡도 분석

• 시간 복잡도: O(4^N) - 각 위치에서 최대 4개의 방향으로 이동할 수 있으며, 총 N번 이동하므로 지수 시간 복잡도를 가집니다. visited 배열을 통해 이미 방문한 곳은 탐색하지 않으므로 실제 탐색하는 노드 수는 가지치기되어 줄어들지만, 최악의 경우 모든 경로를 탐색할 수 있습니다.
• 공간 복잡도: O(N) - DFS 재귀 호출 스택의 깊이가 최대 N이 될 수 있으므로, 스택에 필요한 공간은 O(N)입니다. 또한 visited 배열은 항상 일정한 크기(30x30)를 가지므로, 공간 복잡도에 큰 영향을 미치지 않습니다.

핵심 포인트

1. DFS 및 백트래킹 활용: 가능한 모든 경로를 탐색하기 위해 DFS를 사용하고, 이미 방문한 곳을 다시 방문하지 않도록 백트래킹을 적용합니다.
2. 확률 계산: 각 경로의 확률을 계산하고, 단순한 경로의 확률을 모두 더하여 최종 확률을 구합니다.
3. 방문 기록 관리: visited 리스트를 사용하여 로봇이 방문한 위치를 기록하고, 백트래킹 시 방문 기록을 초기화하여 다른 경로 탐색에 영향을 주지 않도록 합니다.

풀이 코드

import sys
import math
from collections import deque

input = sys.stdin.readline

l, e, w, s, n = map(int, input().split())

e = e/100
w = w/100
s = s/100
n = n/100

visited = [[False]*30 for i in range(30)]
x, y = 15, 15
visited[x][y] = True

def DFS(level,prob,visited,x,y):
    if level == l:
        return prob

    result = 0
    for i in range(4):
        nx,ny = 0,0
        if i == 0:
            ny+=1
            p = e
        elif i == 1:
            ny-=1
            p = w
        elif i == 2:
            nx+=1
            p=s
        elif i == 3:
            nx-=1
            p=n

        if visited[x+nx][y+ny]:
            continue
        
        else:
            visited[x+nx][y+ny] = True
            result += DFS(level+1,prob*p,visited,x+nx,y+ny)
            visited[x+nx][y+ny] = False

    return result

answer = 0
for i in range(4):
    nx,ny = 0,0
    if i == 0:
        ny+=1
        p = e
    elif i == 1:
        ny-=1
        p = w
    elif i == 2:
        nx+=1
        p=s
    elif i == 3:
        nx-=1
        p=n

    visited[x+nx][y+ny] = True
    answer += DFS(1,p,visited,x+nx,y+ny)
    visited[x+nx][y+ny] = False

print(answer)