백준 1300 말이 되고픈 원숭이 파이썬

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

1600번: 말이 되고픈 원숭이

 

원숭이는 말처럼 최대 30번까지만 움직일 수 있다. 가장 먼저 고려해야하는 것은 이것이다.

말처럼 움직여서 먼저 도착한 위치가 있다. 이 위치에 원숭이가 뒤늦게 도착하면, 이 모수는 더 이상 볼 필요가 없을까? 를 고민해야한다. 그런데 말처럼 먼저 도착했는데, 말의 횟수를 다 쓰고 다음은 말로 이동해야만 갈 수 있는 반례가 존재한다. 따라서 말처럼 움직이는 것과 원숭이처럼 움직이는 시간은 다른 형태로 고민을 해야한다.

​

따라서 3차원 배열로 분리 가능한지를 검토해야한다. 원숭이는 말처럼 최대 30번까지만 움직일 수 있고, 배열은 최대 40,000개의 모수를 가진다. 다 합치면 1,200,000개의 모수를 가진다. 메모리와 시간복잡도를 계산했을 때는 충분히 가능하다.

​

따라서 말로 움직일 수 있는 횟수 + 1 만큼 방문 체크 배열을 만들고, 말로 움직인 횟수에 따라서 각기 다른 방문 배열을 운영한다. 방문 배열에 따라 BFS를 돌려서 실제 도착하자마자 값을 출력해주면 된다.

 

 

 

 

import sys
from collections import deque


def bfs(n,m,k):

    # 초기화
    que = deque()
    que.append((0,0,0,0))
    v[0][0][0] = 0

    while que :

        # 현재 위치 확인 및 변수 초기화
        r,c,horse, time = que.popleft()
        next_time = time + 1
        next_horse = horse + 1


        #도착 시 값 출력 (종료 조건)
        if r == n-1 and c == m-1 :
            print(time)
            return

        #원숭이처럼 움직일 때
        for rr, cc in monkey_list:
            next_r, next_c = r+rr, c+cc

            if -1 < next_r < n and -1 < next_c < m:
                #3차원 배열 HORSE 확인
                if my_list[next_r][next_c] == 0 and v[horse][next_r][next_c] > next_time :
                    v[horse][next_r][next_c] = next_time
                    que.append((next_r, next_c, horse, next_time))

        #말처럼 움직일 때
        for rr, cc in horse_list:
            next_r, next_c = r+rr, c+cc

            if next_horse > k :
                break

            if -1 < next_r < n and -1 < next_c < m:
                # 3차원 배열 NEXT_HORSE 확인
                if my_list[next_r][next_c] == 0 and v[next_horse][next_r][next_c] > next_time :
                    v[next_horse][next_r][next_c] = next_time
                    que.append((next_r, next_c, next_horse, next_time))

    #못 도착하면 종료
    print(-1)
    return

# 이동 배열 선언
monkey_list = [[1,0],[-1,0],[0,1],[0,-1]]
horse_list = [[1,2], [2,1], [2,-1],[1,-2], [-1,2],[-2,1], [-1,-2],[-2,-1]]

# 변수 입력
k = int(sys.stdin.readline().rstrip())
m,n = map(int,sys.stdin.readline().split())
my_list = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# 방문 체크용 배열
v = [[[9876543210 for _ in range(m)] for _ in range(n)] for _ in range(k+1)]

# SOLUTION
bfs(n,m,k)