이 문제 처음 읽고 일반환된 코드를 생각하지 못해 틀렸습니다.
중요한 것은 문제에서 이야기한 말 이동의 횟수에 따라 이동할 수 있는 것이 달라진다는 것. 그리고 이걸 방문 배열에서 어떻게 체크할 것인가? 입니다. 만약에 자꾸 틀리신다면, 아래 TEST CASE를 분석해보시면, 느낌이 오실겁니다.. 일반적인 2차원 방문 배열로는 이 문제를 풀 수 없구나..
1
5 5
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즉, 낚시 문제였던 것 같습니다. 다행이 k값을 고려하여 방문 배열을 3차원으로 늘려줬더니 풀리게되었습니다. 물론 Python은 6600ms, PyPy는 600ms로 통과되었는데, Python은 참.. 정말 느린 언어네요.. 조금씩 Kotlin과 C++로 언어를 옮겨야할 것 같습니다..
문제풀이
일단 문제의 조건을 준수합시다.
원숭이는 말처럼 이동 할수도 있고 그냥 상 하 좌 우 격자 이동만 할 수 있습니다. 그리고 말처럼 이동하는 것은 제약 사항이 있습니다. 바로 k번만 이동할 수 있다는 것이죠. 따라서 이 모두를 고려 해야 합니다.
그러면 어떤 이동이 우선이 되어야 할까요?
제 생각이지만 상 하 좌 우 격자 이동이 우선시 되어야 할 것 같습니다. 그 이유는 위에서 제시된 Test Case에서는 상 하 좌 우로만 이동하다가 마지막에 말 점프를 합니다. 말 점프를 먼저하게 되면, 방금 말씀드린 경로를 찾을 수 없게 됩니다. 따라서 격자 이동을 먼저 하고 말 이동을 하는 것이 모든 경로를 고려할 수 있다고 생각했습니다.
그러면 방문 배열
1 차원: 말이동을 몇번 했는지
2 차원: 행
3 차원: 열
로 구성하여 BFS 탐색을 시도한다면 도착 지점까지의 가장 빠른 경로를 탐색할 수 있습니다.
따라서 전체 코드는 아래와 같이 구성됩니다.
전체 코드
from collections import deque
import sys
input = sys.stdin.readline
k = int(input())
w, h = map(int, input().split())
INF = int(1e9)
arr = [list(map(int, input().split())) for _ in range(h)]
visited = [[[INF for _ in range(w)] for _ in range(h)] for _ in range(k+1)]
delta = [(0, 1), (1, 0), (0, -1), (-1, 0)]
horse_delta = [
(-1, -2),
(-2, -1),
(-1, 2),
(-2, 1),
(1, 2),
(2, 1),
(2, -1),
(1, -2)
]
sx, sy = 0, 0
ex, ey = h-1, w-1
def bfs(sx, sy):
q = deque([(sx, sy, 0, 0)])
while q:
x, y, cnt, c = q.popleft()
if x == ex and y == ey:
return cnt
for i in range(4):
nx, ny = x + delta[i][0], y + delta[i][1]
if not (0 <= nx < h and 0 <= ny < w): continue
if arr[nx][ny] == 1: continue
if visited[c][nx][ny] != INF : continue
visited[c][nx][ny] = cnt + 1
q.append((nx, ny, cnt + 1, c))
if c >= k: continue
for i in range(8):
nx, ny = x + horse_delta[i][0], y + horse_delta[i][1]
if not (0 <= nx < h and 0 <= ny < w): continue
if arr[nx][ny] == 1: continue
if visited[c+1][nx][ny] != INF: continue
visited[c+1][nx][ny] = cnt + 1
q.append((nx, ny, cnt + 1, c + 1))
return -1
print(bfs(sx, sy))질문과 오타 수정 언제나 환영입니다.
