[파이썬] 백준 1405 : 미친로봇 (골드4)

[파이썬] 백준 1405 : 미친로봇 (골드4)

1405번: 미친 로봇

---

문제

---

풀이

0. 방향성 생각

• 백트래킹 기본 4**14 = 2*28 = 250만 탐색 경우의수 많다 -> 백트래킹 가지치기

1. 입력

temp = list(map(int, input().split()))
n,prob = temp[0],list(map(lambda x: x/100, temp[1:]))

visit = [[False]*29 for _ in range(29)]
visit[14][14] = True

step = [(1,0),(-1,0),(0,1),(0,-1)]
count = 0

• 이동할 수 있는 배열 visit에 False 할당
• 원점 14,14를 True로 하고 동서남북 인덱스에 맞게 step 지정

2. DFS 함수 정의

def dfs(x,y,t,p):
    
    global count
    
    if t == n:
        count += p
        return

    for i in range(4):
        dx,dy = step[i]
        nx,ny = x+dx, y+dy

        if not visit[ny][nx]:
            visit[ny][nx] = True
            dfs(nx,ny,t+1,p*prob[i])
            visit[ny][nx] = False

dfs(14,14,0,1.0)
print(count)

• 안겹치고 마지막에 도달하면 확률을 count에 더해준다.

---

전체코드

temp = list(map(int, input().split()))
n,prob = temp[0],list(map(lambda x: x/100, temp[1:]))

visit = [[False]*29 for _ in range(29)]
visit[14][14] = True

step = [(1,0),(-1,0),(0,1),(0,-1)]
count = 0

def dfs(x,y,t,p):
    
    global count
    
    if t == n:
        count += p
        return

    for i in range(4):
        dx,dy = step[i]
        nx,ny = x+dx, y+dy

        if not visit[ny][nx]:
            visit[ny][nx] = True
            dfs(nx,ny,t+1,p*prob[i])
            visit[ny][nx] = False

dfs(14,14,0,1.0)
print(count)

 

코멘트

백트래킹 기본

다시 풀어봤는데 set 이용해서 방문처리 했는데 map size가 크지 않아서 훨씬 느려지긴 했음

set이랑 dict은 웬만하면 피하자