인프런 커뮤니티 질문&답변
작성한 질문수
3-D 시간초과와 range based for
작성
·
270
·
수정됨
0
안녕하세요 큰돌님 몸은 괜찮으신지요. 문제를 풀다가 index out of bound도 아닌 segmentation fault가 떠서 헤매고 있습니다.
코드 한 번 봐 주시면 감사하겠습니다.
http://boj.kr/28b2fc7b2381489fb1ba98f2299c5906
range based for문에서 데이터를 추가해 이상한 값이 들어가 오류가 나는 거 였습니다.
cpp에서 range based for문이 어떻게 실행되길래 이런 현상이 발생하나요? range based for에서는 수정도 되지 않던데 말이지요. reference를 읽어도 모르겠어서 여쭈어 봅니다.
또한 제 코드가 왜 시간 초과가 나는지 모르겠습니다. dfs두개에 여러 로직들로 O(k(n)^2) 아닌가요? 72 ~ 77라인은 결국 ny, nx가 조건을 만족 할때 하는거라 n^3이 되지않는다고 보입니다. 이 라인들을 64번 for문 밖으로 빼면 72~ 77 라인의 시간 복잡도는 n^2이라고 생각는데 말이지요.
답변 1
0
안녕하세요 태완님 ㅎㅎ
걱정해주셔서 감사합니다. ㅎㅎ 통원치료중이에요. ㅎㅎ
cpp에서 range based for문이 어떻게 실행되길래 이런 현상이 발생하나요? range based for에서는 수정도 되지 않던데 말이지요. reference를 읽어도 모르겠어서 여쭈어 봅니다.
>> 음.. 이해가 잘안가는데 어떤 부분인지 다시 질문해주실 수 있나요?
2. 시간초과
>> 제 생각에는 이부분이 불필요해서 시간초과가 나는 것 같습니다.
혹시 고쳐보시겠어요?
로직은 문제 없는 것같아요.
//왜 굳이? escape는 불필요한 자료구조
if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
escape.push_back({i, j});
}
}
else{
ls[i][j] = 0;
h_cor.push({i, j});
//또다시? 이부분을 만약 할거면 아 if문 바끙로 뺴서 i와 j를 체크하는게 좋다.
if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
escape.push_back({i, j});
}
}
}
}
for(auto pa : escape){
if(pa.first == h_cor.front().first && pa.second == h_cor.front().second){
cout << 1;
exit(0);
}
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.