글 읽기 - 17836번 시간 초과 질문

junhyung9985 1년 전 0

제가 아는 한 시간을 최소로 단축시킬려고 코드를 짜봤는데 여기서 어떻게 더 시간단축을 할 수 있는지 모르겠습니다.

혹시 제 코드에 비효율적 부분을 지적해주실 수 있다면 감사드리겠습니다.

(아니면 혹시 제 코드가 틀려서 반례를 찾아주실 수도 있다면 정말로 고마울 것 같습니다!)

#include <iostream>
#include <queue>
#include <tuple>
#define INF 10001

using namespace std;

short N, M;
char m[100][100] ={1}; // 지도
short tm[100][100] = {0}; // {현재까지 걸린 시간}
char dx[4] = {1,0,-1,0};
char dy[4] = {0,1,0,-1};
priority_queue<tuple<short,bool, char, char>> pq; // {(-1) * 현재까지 걸린 시간, 그람 소지여부, y좌표, x좌표}


int main() {

  ios_base :: sync_with_stdio(0);
  cin.tie(0);
  
  short T;
  short foo;
  char y, x;
  bool gram;
  short t;

  
  cin >> N >> M >> T;

  for (short i = 0; i<N; i++)
    for (short j = 0; j< M; j++){
      cin >> foo;
      m[i][j] = foo;
      tm[i][j] = foo != 1 ? INF : 0; // 벽인 부분은 갈 수 없도록 최소 걸리는 시간을 0으로 표시하여 방문 안 하도록     
    }

  pq.push({0,0,0,0});
    
  while(!pq.empty()){
    y = get<2>(pq.top());
    x = get<3>(pq.top());
    gram = get<1>(pq.top());
    t = -get<0>(pq.top());
    pq.pop();
    if(t > T) break;
    tm[y][x] = t;
    if (x == M-1 && y == N-1){
      break;
    }
    if(gram){
      if(y < N-1) pq.push({-t-1,1,y+1,x});
      else if (x < M-1) pq.push({-t-1,1,y,x+1}); 
      continue;        
    } // 그람을 갖고 있다면
    
    for (char i =0 ; i <4; i++){
      if(x == 0 && i == 2) continue;
      if(x == M-1 && i == 0) continue;
      if(y == 0 && i == 3) continue;
      if(y == N-1 && i == 1) continue;
      // IndexOutofBound 처리
        
      if(tm[y+dy[i]][x+dx[i]] <= t+1) continue; // 더 짧은 시간 내에 해당 칸으로 갈 수 있는거라면
      else if(m[y+dy[i]][x+dx[i]] == 2){
        pq.push({-t-1,1,y+dy[i],x+dx[i]});
      } // 그람 소지하게 될 때
      else{
        pq.push({-t-1,0,y+dy[i],x+dx[i]});
      }

    }
    
    
  }
  
  if(T >= tm[N-1][M-1]) cout << tm[N-1][M-1] << "\n";
  else cout << "Fail\n";
  
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17836번 시간 초과 질문

junhyung9985 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말