반응형
풀이
백트래킹을 활용해서 해결할 수 있는 문제다. 먼저 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)
반응형
'Algorithm > Baekjoon' 카테고리의 다른 글
15591. MooTube (Silver) (0) | 2022.03.18 |
---|---|
15997. 승부 예측 (Python) (0) | 2022.03.15 |
2616. 소형기관차 (Python) (0) | 2022.03.13 |
1655. 가운데를 말해요 (Python) (0) | 2022.03.12 |
3078. 좋은 친구 (Python) (0) | 2022.03.10 |
댓글