치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다
평소에 문제 번호만 읽은 뒤 혼자 풀어보고 안풀리면 강의를 참고하면서 공부 중인데요,
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
13
2
코딩살구클럽
0
16
1
코딩살구클럽 문의
0
27
2
코딩살구클럽 승인
0
31
2
DP 경우의 수 설명이 이해가 되지 않습니다.
0
32
2
3-F 채점 관련 질문
0
29
1
BFS, DFS 활용이 되는 상황에서의 방향성
0
32
2
코딩살구클럽 승인
0
42
2
코딩살구클럽승인
0
38
3
코딩살구클럽 승인
0
50
2
3-D 관련 질문
0
35
2
코살구 회원가입 문의
0
45
2
코살구 로그인 문제
0
65
2
3-A 문제 풀이 관련 질문
0
56
3
2-O 질문 있습니다
0
38
2
2-T 문제에 관한 질문
0
40
2
코딩 살구 클럽 접속 및 사용방법 문의
0
63
2
안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~
0
64
2
코딩살구클럽 로그인문제
0
78
3
코딩 살구 클럽 로그인 문제
0
85
2
2-J 채점관련 질문
0
67
3
코딩 살구 클럽 Python 지원 가능 여부
0
77
1
살구클럽 아이디 없음 문제
0
76
1
1-O 코딩살구클럽 채점관련 질문
0
61
2