[문제 바로가기] https://www.acmicpc.net/problem/1405
📌문제 설명
통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.
각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.
로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)
입력
첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.확률의 단위는 %이다.
출력
첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.
💡 문제 풀이
DFS + 재귀로 해결한 문제다.
문제만 잘 읽으면 DFS 변형도 아닌 단순한 DFS 구현 문제(?)임을 알 수 있다.
step 1)
변수 선언
- probability : 동서남북 방향으로 이동할 확률들을 담은 배열
- answer : 확률의 총 합을 담을 변수
step 2)
이 문제의 핵심은 좌표와 상관없이 (미친?) 로봇이 지나갔던 길을 되돌아가지 않기만 하면 된다.
즉, N만큼 이동하더라도 중복된 좌표가 존재하지 않으면 단순한 이동경로가 된다.
dfs 함수의 진행은 다음과 같다.
- 종료 조건 : visited 길이가 N+1이면 종료한다.(시작점을 포함했으므로 N+1)
- 4방향으로 이동할 때, 이동하고자 하는 좌표가 visited에 존재하지 않으면 visited에 추가하고 다음 재귀로 진행한다.
- 다음 방향 탐색을 위해 추가한 좌표는 바로 pop 해준다.
dfs를 진행하면서 방향(동서남북)에 알맞는 확률을 곱해주면서 진행한다.
재귀 종료시 answer 변수에 지금까지 누적한 확률을 더해준다.
step 3)
주어진 확률은 '%단위'로 주어졌기 때문에 answer에 (0.01) ** N 을 곱해주고 출력한다.
코드는 다음과 같다.
d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 4방향 탐색
def dfs(r, c, visited, total):
global answer
if len(visited) == N+1:
answer += total
return
for idx in range(4):
nr = r + d[idx][0]
nc = c + d[idx][1]
if (nr, nc) not in visited:
visited.append((nr, nc))
dfs(nr, nc, visited, total*probability[idx])
visited.pop()
N, ep, wp, sp, np = map(int, input().split())
probability = [ep, wp, sp, np]
answer = 0
dfs(0, 0, [(0, 0)], 1)
print(answer * (0.01 ** N))DFS로 풀어야 하는 건 알았지만 visited를 좌표로 접근해도 된다는 것을 빨리 깨우치지 못했다... (어짜피 어떤 좌표든 중복만 안되면 되기 때문!)
문제를 좀 더 차분히 읽고 접근하자.
