[골드5] 17836번 : 공주님을 구해라!

🛠 문제

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

👩🏻‍💻 해결 방법

처음에는 bfs 인자값에 옵션을 두어 옵션에 따라 bfs가 실행되도록 했는데 엄청난 시간초과가 났었다..;;
따라서 그람을 사용하지 않는 경우는 따로 시간을 저장하는 변수 대신 visit 배열에 +1씩 하면서 구하였고,
그람을 사용하는 경우는 그람 도달 전까지의 시간과 그람을 사용해서 마지막 지점까지 가는 시간의 합을 gramT 변수에 저장하여 구하였다
마지막 지점에 도달하면 최솟값을 return하고 도달하지 못하면 gramT를 return한다

소스 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m, T = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

visit = [[0] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
gramT = 100001

def bfs():
  global gramT
  q = deque()
  q.append((0, 0))
  visit[0][0] = 1

  while q:
    x, y = q.popleft()

    if x == n-1 and y == m-1:
      return min(visit[x][y]-1, gramT)

    if graph[x][y] == 2:
      gramT = n-1-x + m-1-y + visit[x][y]-1

    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<n and 0<=ny<m and graph[nx][ny] != 1:
        if visit[nx][ny] == 0:
          visit[nx][ny] = visit[x][y] + 1
          q.append((nx, ny))
  return gramT

result = bfs()
print("Fail" if result > T else result)