이번 문제는 BFS를 통해 해결하였다. BFS를 통해 좌표를 탐색하며 방문처리를 한다. 방문처리를 할 때에는 그때까지 걸린 시간을 방문처리 값으로 넣고, 다음 좌표의 방문 여부를 판단할 때, 다음 좌표의 방문처리값과 현재 시간+1을 비교하여 방문처리값이 더 클 때에만 방문하도록 하였다. 그리고 검을 만나면 벽과 상관없이 이동이 가능하므로 결과변수를 현재시간 + 좌표값 계산 결과와 결과변수 중의 작은 값으로 갱신한다. (n-1, m-1)에 도달하였을 때에는 결과변수와 현재 시간 중 더 작은 값을 결과변수로 갱신해준다. 이 과정이 끝난 후, 결과변수가 초기값이라면 Fail을 출력하도록, 아니라면 범위를 확인하여 값을 출력하도록 하였다.

Code

from collections import deque
n, m, t = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def bfs():
    q = deque()
    q.append((0, 0, 0, False))
    visited = [[1e9 for _ in range(m)] for _ in range(n)]
    visited[0][0] = 0
    result = 1e9
    while q:
        y, x, time, flag = q.popleft()
        if (y, x) == (n-1, m-1):
            result = min(result, time)
            continue
        if flag:
            result = min(result, time+abs(n-1-y)+abs(m-1-x))
            continue
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] > time+1:
                if flag:
                    visited[ny][nx] = time+1
                    q.append((ny, nx, time+1, flag))
                else:
                    if grid[ny][nx] != 1:
                        if grid[ny][nx] == 2:
                            flag = True
                        visited[ny][nx] = time+1
                        q.append((ny, nx, time+1, flag))
    if result == 1e9:
        return -1
    return result
answer = bfs()
if 0 <= answer <= t:
    print(answer)
else:
    print("Fail")