[파이썬] 백준 1600 : 말이 되고픈 원숭이 (골드3)

[파이썬] 백준 1600 : 말이 되고픈 원숭이 (골드3)

1600번: 말이 되고픈 원숭이

---

문제

---

풀이

0. 방향성 생각

• 3차원 visit만들어서 visit[점프사용횟수][y][x] = 시간 저장
• BFS

1. 입력

from collections import deque

k = int(input())
w,h = map(int,(input().split()))
INF = w*h
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[[INF]*w for _ in range(h)] for _ in range(k+1)]
step = [(1,0),(0,1),(-1,0),(0,-1),(2,1),(-2,1),(1,2),(-1,2),(2,-1),(-2,-1),(1,-2),(-1,-2)]

• 4가지 방향 + 점프 8방향 정의

2. BFS 탐색

q = deque([(0,0,0,0)])
visit[0][0][0] = 0
while q:
    
    t,x,y,jump = q.popleft()
    if (x,y) == (w-1,h-1):
        print(t)
        break
    
    for i in range(12):
        dx,dy = step[i]
        nx = x + dx
        ny = y + dy
        if 0<=nx<w and 0<=ny<h and not arr[ny][nx]:
            if i<4 and t+1 < visit[jump][ny][nx]:
                q.append((t+1,nx,ny,jump))
                visit[jump][ny][nx] = t+1
            elif i>3 and 0<=jump<k and t+1 < visit[jump+1][ny][nx]:
                q.append((t+1,nx,ny,jump+1))
                visit[jump+1][ny][nx] = t+1
else: print(-1)

• 범위 내에 있고 벽이 아닌 경우 이동 가능.
• 1칸 이동인 경우 갱신 가능할 때에만 큐에 넣는다.
• 점프인 경우 점프 횟수가 남아있고 갱신 가능한 경우에만 넣는다.

 

---

전체코드

from collections import deque

k = int(input())
w,h = map(int,(input().split()))
INF = w*h
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[[INF]*w for _ in range(h)] for _ in range(k+1)]
step = [(1,0),(0,1),(-1,0),(0,-1),(2,1),(-2,1),(1,2),(-1,2),(2,-1),(-2,-1),(1,-2),(-1,-2)]

q = deque([(0,0,0,0)])
visit[0][0][0] = 0
while q:
    
    t,x,y,jump = q.popleft()
    if (x,y) == (w-1,h-1):
        print(t)
        break
    
    for i in range(12):
        dx,dy = step[i]
        nx = x + dx
        ny = y + dy
        if 0<=nx<w and 0<=ny<h and not arr[ny][nx]:
            if i<4 and t+1 < visit[jump][ny][nx]:
                q.append((t+1,nx,ny,jump))
                visit[jump][ny][nx] = t+1
            elif i>3 and 0<=jump<k and t+1 < visit[jump+1][ny][nx]:
                q.append((t+1,nx,ny,jump+1))
                visit[jump+1][ny][nx] = t+1
else: print(-1)

 

코멘트

pypy3.