[백준-파이썬] 1405 : 미친 로봇

문제 보러 가기!

간단 소감

오랜만에 dfs 문제를 풀어서 재밌었다 ㅎㅎ
그리고 visited 아이디어를 생각하는 것도 특이하고 재밌었다~~

문제 설명

로봇이 4방향(동서남북) 중 한 방향으로 N번 이동한다.
각 방향으로 이동할 확률을 준다.
같은 곳을 또 방문하면 이동 경로가 단순하지 않다고 한다.
로봇의 이동 경로가 단순할 확률을 구하는 문제였다.

풀이

로봇이 4방향으로 N번 이동하고, N이 14보다 작다고 해서 딱 순열! 이 생각났다. DFS로 각 방향을 가봤다. dfs를 할 때 가지고 다니는 변수는 지금까지 몇 번 이동했는지, 현재 인덱스, 현재 위치까지 이동할 확률.
그런데 로봇이 단순하지 않은 경로로 이동할 경우, 더이상 볼 필요 없이 리턴해주면 되니까 백트래킹이라고도 할 수 있겠다.

visited를 2차원으로 생각해야 한다. 가운데에서 로봇이 출발했다고 가정하고 N이 최대 14니까 같은 방향으로 쭉~ 가도 14번 가는 것이다. 그럴 때 visited 영역을 넘어가지 않도록 !! visited 판은 인덱스 0~28로 해줬고, 출발은 14, 14에서 하게 했다.

주의

• 출발지도 방문 체크하는 것!

코드

import sys

input = sys.stdin.readline

N, dong, seo, nam, buk = map(int, input().split())
direct_percent = [dong * 0.01, seo * 0.01, nam * 0.01, buk * 0.01]
direct = [(0, 1), (0, -1), (1, 0), (-1, 0)]

simple = 0
visited = [[False] * 29 for _ in range(29)]
visited[14][14] = True  # 출발지도 방문한 곳!


def dfs(cnt, i, j, now_percent):
    global simple
    if cnt == N:
        simple += now_percent
        return

    for k in range(4):
        ni, nj = i + direct[k][0], j + direct[k][1]
        # 방문했던 곳에 다시 방문하면 단순하지 않음
        if visited[ni][nj] == True:
            continue
        visited[ni][nj] = True
        dfs(cnt + 1, ni, nj, now_percent * direct_percent[k])
        visited[ni][nj] = False


dfs(0, 14,14, 1)

print(simple)