소프티어

BFS로 풀어도 시간초과가 걸리지 않는 문제 아닌가요?

테스트 케이스 전체중에 50프로 문제가 1.1초에서 시간초과라고 걸리는데

이유를 모르겠습니다.

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

int N;

int arr[1001][1001];

void bfs(int x, int y){

  queue<pair<pair<int,int>,pair<long long,int>>> q;

  int mv[2][2] = {{0,1}, {1,0}};

  int ma=0;

  q.push({{x,y}, {arr[x][y],0}});

  q.push({{x,y}, {arr[x][y]*2,1}});

  while(!q.empty()) {

    int st_x = q.front().first.first;

    int st_y = q.front().first.second;

    int check = q.front().second.second;

    int hap = q.front().second.first;

    q.pop();

    if(st_x == N-1 && st_y==N-1) {

      ma = max(ma,hap);

    } else {

      for(int i=0; i<2; i++) {

        int dx = st_x + mv[i][0];

        int dy = st_y + mv[i][1];

        if(dx>=0 && dy>=0 && dx<N && dy<N) {

          q.push({{dx,dy},{hap+arr[dx][dy], check}});

          if (check==0) {

            q.push({{dx,dy},{hap+arr[dx][dy]*2, 1}});

          }

        }

      }

    }

  }

  cout << ma;

}

int main(int argc, char** argv)

{

  cin.tie(NULL);

  cout.tie(NULL);

  ios_base::sync_with_stdio(false);

  cin >> N;

  for(int i=0; i<N; i++) {

    for(int j=0; j<N; j++) {

      cin >> arr[i][j];

    }

  }

  bfs(0,0);

  return 0;

}