치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다
평소에 문제 번호만 읽은 뒤 혼자 풀어보고 안풀리면 강의를 참고하면서 공부 중인데요,
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만 번 반복하기 때문에 시간에는 문제가 없는 수준
>> 네 맞습니다. 그렇게 보면 괜찮은데요.
문제는 시간초과가 났다는 것이고 시간초과를 해결하는 방법은 비효율적인 코드를 개선하는 것뿐입니다. 문제마다 시간초과의 상한선은 각각 다르고 이걸 파악하는 것은 쉽지 않아서요.
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
30
2
2주차 개념#12 트리 순회
0
20
2
백준사이트가 종료된다고 합니다.
0
245
2
백준 서비스 종료
9
780
1
sk 하이닉스 코테 대비
0
360
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
100
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
166
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
50
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
52
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
89
2
5-Q 질문
0
63
2
풀이 코드 질문
0
64
2