-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
거리배열을 따로 만드는 경우 타임리밋
21.05.05 11:51 작성 조회수 181
0
안녕하세요. 수업 잘 듣고 있습니다.
체크배열에 정점까지 도달하는 데 필요한 횟수를 저장하는 게 헷갈려서, dis배열을 따로 만들어봤습니다.
그랬더니 타임리밋이 걸리더라고요.
제가 보기엔 연산 속도에 큰 차이가 날 것 같지 않은데,
이렇게 배열 두 개를 사용할 경우 타임리밋이 걸리는 이유가 궁금합니다.
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int ch[10001], dis[10001], d[3]={1, -1, 5};
int main(void){
//freopen("input.txt", "rt", stdin);
int i, n, m, x, pos;
queue<int> Q;
scanf("%d %d", &n, &m);
ch[n] = 1;
Q.push(n);
while(!Q.empty()){
x = Q.front();
Q.pop();
for(i=0; i<3; i++){
pos = x+d[i];
if(pos<= 0 || pos>10000) continue;
if(ch[pos]==0){
dis[pos] = dis[x] + 1;
Q.push(pos);
}
if(pos==m){
printf("%d", dis[pos]);
exit(0);
}
}
}
return 0;
}
답변을 작성해보세요.
답변 1