[백준 1600번] 말이 되고픈 원숭이(파이썬)

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

이 문제를 처음 보고

오만가지 생각을 다 했습니다.

최대 K번만큼 원숭이가 말처럼 움직인다라...

그럼 원숭이가 움직일 때마다

있는 지점에서 상하좌우 이동+말이동

이걸 다 봐야하나?

그럼 K번만큼 움직이는 건 어떻게 구하지??

시간초과 엄청날텐데...

문제의 접근조차 하지못해서

상당히 애를 먹었다가

이 문제에서 힌트를 얻었습니다.

2022.06.30 - [알고리즘 공부] - [백준 7569번 ] 토마토 2(파이썬)

[백준 7569번 ] 토마토 2(파이썬)

바로 이 문제.

3차원으로 visited를 볼 수 있다라...

오호! 잠깐만!

말 이동하는 걸 visited에 반영해서

가로x세로x말이동횟수

이렇게 해서 3차원으로 구현해볼까?

라는 아이디어를 떠올렸습니다.

 

#백준 1600번 말이 되고픈 원숭이
from collections import deque

K=int(input())
W,H=map(int,input().split())

room=[list(map(int,input().split())) for _ in range(H)]
visited=[[[0]*W for _ in range(H)] for _ in range(K+1)]

dx=[0,0,1,-1]
dy=[1,-1,0,0]
horse=[[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1]]

q=deque()
q.append([0,0,0])


def bfs():
    while q:
        x,y,cnt=q.popleft()
        if x==H-1 and y==W-1:
            return (visited[cnt][H-1][W-1])
        #1. 상하좌우로 움직이는 경우
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]

            if nx<0 or nx>=H or ny<0 or ny>=W:
                continue

            if room[nx][ny]==1:
                continue

            if not visited[cnt][nx][ny]==0:
                continue

            visited[cnt][nx][ny]=visited[cnt][x][y]+1
            q.append([nx,ny,cnt])
        #2. 원숭이 이동을 쓰는 경우
        if cnt<K:
            for d in range(8):
                nx=x+horse[d][0]
                ny=y+horse[d][1]

                if nx < 0 or nx >= H or ny < 0 or ny >= W:
                    continue

                if room[nx][ny] == 1:
                    continue

                if not visited[cnt+1][nx][ny] == 0:
                    continue
                #말 이동을 수행했으므로 cnt+1로 올림.
                visited[cnt+1][nx][ny]=visited[cnt][x][y]+1
                q.append([nx,ny,cnt+1])


    return -1

print(bfs())

이 문제같은 경우에는

3차원 배열을 쓰는 아이디어가 없다면

상당히 오랜 시간 해매기 쉬웠습니다.

이 문제를 공부하면서

3차원 배열 사용법을 공부하셔도 좋습니다.