치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다
평소에 문제 번호만 읽은 뒤 혼자 풀어보고 안풀리면 강의를 참고하면서 공부 중인데요,
http://boj.kr/643383b66dea47fdac83a802a5ed1c3f
해당 코드에서 치즈 녹이는 로직을
0인 칸을 dfs로 돌면서 상하좌우에 1인 칸이 있으면 해당 칸을 2로 변경(0으로 바로 변경하면 다른 칸에서 마주칠때 문제가 생길 수 있으므로)
dfs를 마친 뒤 recover함수에서 arr을 돌면서 2인 부분을 0으로 변경
이런 방식으로 구현을 했는데 아무리 코드를 최적화 해봐도 계속 시간초과가 발생했습니다. 도저히 안돼서 큰돌님 강의를 보고 벡터에 좌표를 저장해 해결한 코드가 아래 링크입니다.
http://boj.kr/f4f738238bdb453bbf9a967627ddb912
강의를 참고해 문제를 해결하긴 했는데, 왜 첫 번째 방법이 더 느린지, 혹시 첫 번째 방법으로도 시간초과에 걸리지 않게 짤 수가 있을지 궁금해서 질문합니다!
답변 1
0
안녕하세요 경로님 ㅎㅎ
void recover(){
for(int x = 0; x < n; x++){
for(int y = 0; y < n; y++){
if(arr[x][y] == 2) arr[x][y] = 0;
}
}
}
제 생각에는 cheescount보다는 이부분이 시간초과가 뜬 것 같습니다. 매번 맵 전체를 탐색하니까 시간초과가 뜨는 것인데요. 녹는 부분만 바꿔주도록 효율적으로 고쳐야 합니다.
감사합니다.
0
제가 코드를 작성할 때 그 부분을 생각해 보았습니다. n의 크기가 최대 100이라 for문을 만번 돌고 main함수의 while문은 모든 칸에 치즈가 꽉 차 있을 경우에 제일 오래 걸릴 테니 최대 49번이라 아무리 오래 걸린다고 해도 49만 번 반복하기 때문에 시간에는 문제가 없는 수준이라고 생각했는데 혹시 반복 횟수가 잘못 계산되었다거나 시간이 더 걸릴 부분이 있을까요?
0
49만 번 반복하기 때문에 시간에는 문제가 없는 수준
>> 네 맞습니다. 그렇게 보면 괜찮은데요.
문제는 시간초과가 났다는 것이고 시간초과를 해결하는 방법은 비효율적인 코드를 개선하는 것뿐입니다. 문제마다 시간초과의 상한선은 각각 다르고 이걸 파악하는 것은 쉽지 않아서요.
코딩살구클럽 가입부탁드립니다
0
27
2
코딩살구클럽 가입 요청 확인부탁드립니다
0
30
2
5-S 테스트 케이스 질문
0
34
2
코살 문제풀이 환경
0
48
2
2 - T 오큰수 문제가 있는 것 같습니다.
0
43
1
추천 추가문제들
0
43
2
프로그래머스 코테 환경 관련해서 질문드립니다.
0
45
2
해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.
0
41
2
균형 이진 트리 설명 시 높이 숫자
0
31
2
4-H 질문드립니다.
0
35
2
1-K 질문드립니다.
0
41
2
대기업 인적성 시험 질문
0
41
2
4-C 질문드립니다
0
41
2
[수학숙제 / BOJ 2870] 채점 서버 오작동
0
37
1
코테 준비 질문
0
50
1
살구클럽가입 요청드려요
0
39
2
1-I 문제 질문
0
40
2
코딩살구클럽 가입
0
57
2
AI 코딩 도구 사용 시 학습 방법 조언
0
52
2
코딩살구클럽 오류
0
61
2
코살클 [3-F 괄호 추가하기] 프라이빗 9번 제보
0
46
1
코딩살구클럽 테스트 케이스 오류 제보
0
52
2
삼성 코딩테스트
0
65
2
틀린 이유를 못찾겠습니다
0
48
2