https://www.acmicpc.net/problem/1600
격자판의 맨 왼쪽 위에서 맨 오른쪽 아래까지 원숭이가 이동을 한다.
원숭이는 한 번에 상하좌우로 한 칸씩만 이동할 수 있는데 말에 빙의해서 체스의 나이트처럼(장애물도 건너뛴다. 거의 순간이동) 움직일 수도 있다. 다만 k번으로 횟수가 제한되어있다.
원숭이가 도착 지점에 도착할 때까지 이동했을 때 움직인 최소 횟수를 구해야한다. 못가는 경우도 있다.
너비우선탐색에 횟수 제한이 있는 텔레포트가 생겨 복잡해졌다.
처음에는 원숭이가 방문한 곳을 체크하는 2차원 visited 배열에 이동 횟수와 남은 텔레포트 횟수를 함께 기록하면서 해결해보려했다. 예제로 주어진 테스트 케이스들은 통과했지만 제출했을 때는 통과하지 못해 반례를 찾아보았다.
k = 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0내 처음 코드는 위와 같은 경우에 도착을 하지 못한다는 결과를 내뱉었다. 초반에 텔레포트를 써버리고 벽에 막혀 가지 못한다는 결론을 내버리는 것이었다. 그래서 어떻게 해야할지 고민하다가 visited를 한 차원 높여 2층으로 만들고 1층에는 원숭이의 무빙을 2층에서는 말의 무빙을 기록해보기로 했다. 근데 이렇게 했을 때는 k의 숫자가 더 커졌을 때 제대로 작동하지 못할 것이라 생각이 들어서 코드를 짜기 전에 멈췄다.
다음으로 연달아 떠올린 방법은, k만큼 visited을 쌓아올려서 (3차원이라는 뜻) 남은 k에 해당하는 층에 기록을 하는 방식이었다. 만약 k가 5일 때 말 점프를 쓰지 않고 원숭이 무빙을 하면 visited 5층에 기록될 것이고 말 점프를 하면 visited 4층에 기록되는 방식이다. 사실 이 방법에 대해 큰 확신은 갖지 못하고 예전에 뭔가 비슷한 느낌의 문제를 풀어본 것 같아서 일단 코드를 작성해보았다.
작성한 후 제출해보았을 때 시간초과가 났다. 아무리 생각해도 줄일 방법이 떠오르지 않아 pypy3으로 바꿔서 제출했더니 통과가 됐다...
from sys import stdin
from collections import deque
k = int(stdin.readline())
w, h = map(int, stdin.readline().split())
g = [list(map(int, stdin.readline().split())) for i in range(h)]
start = [0, 0]
end = [h-1, w-1]
q = deque()
q.append([start, k])
#원숭이의 움직임
mx = [1, 0, -1, 0]
my = [0, 1, 0, -1]
#말의 움직임
hx = [1, 2, 2, 1, -1, -2, -2, -1]
hy = [-2, -1, 1, 2, 2, 1, -1, -2]
visited = [[[-1 for i in range(w)] for i in range(h)] for i in range(k + 1)]
def check_range(x, y):
if 0 <= x < h and 0 <= y < w:
return True
return False
visited[k][0][0] = 0
result = -1
flag = False
while q:
now = q.popleft()
if now[0][0] == end[0] and now[0][1] == end[1]:
result = visited[now[1]][now[0][0]][now[0][1]]
break
for i in range(4):
nx = now[0][0] + mx[i]
ny = now[0][1] + my[i]
m = now[1]
if check_range(nx, ny) and g[nx][ny] == 0 and visited[m][nx][ny] == -1:
q.append([[nx,ny], m])
visited[m][nx][ny] = visited[m][now[0][0]][now[0][1]] + 1
if nx == end[0] and ny == end[1]:
result = visited[m][nx][ny]
flag = True
break
if flag:
break
if now[1] > 0:
for i in range(8):
nx = now[0][0] + hx[i]
ny = now[0][1] + hy[i]
m = now[1]
if check_range(nx, ny) and g[nx][ny] == 0 and visited[m - 1][nx][ny] == -1:
q.append([[nx,ny], m - 1])
visited[m - 1][nx][ny] = visited[m][now[0][0]][now[0][1]] + 1
if nx == end[0] and ny == end[1]:
result = visited[m - 1][nx][ny]
flag = True
break
if flag:
break
print(result)
'''
코드는 굉장히 난잡하게 작성되었다. 생각나는대로 막 짰기때문에.!
어떻게 잘 하면 정리할 수는 있을 것 같다.