치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-Q

해결된 질문

작성

281

수정됨

평소에 문제 번호만 읽은 뒤 혼자 풀어보고 안풀리면 강의를 참고하면서 공부 중인데요,

http://boj.kr/643383b66dea47fdac83a802a5ed1c3f

해당 코드에서 치즈 녹이는 로직을

0인 칸을 dfs로 돌면서 상하좌우에 1인 칸이 있으면 해당 칸을 2로 변경(0으로 바로 변경하면 다른 칸에서 마주칠때 문제가 생길 수 있으므로)
dfs를 마친 뒤 recover함수에서 arr을 돌면서 2인 부분을 0으로 변경

이런 방식으로 구현을 했는데 아무리 코드를 최적화 해봐도 계속 시간초과가 발생했습니다. 도저히 안돼서 큰돌님 강의를 보고 벡터에 좌표를 저장해 해결한 코드가 아래 링크입니다.

http://boj.kr/f4f738238bdb453bbf9a967627ddb912

강의를 참고해 문제를 해결하긴 했는데, 왜 첫 번째 방법이 더 느린지, 혹시 첫 번째 방법으로도 시간초과에 걸리지 않게 짤 수가 있을지 궁금해서 질문합니다!

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 경로님 ㅎㅎ

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보다는 이부분이 시간초과가 뜬 것 같습니다. 매번 맵 전체를 탐색하니까 시간초과가 뜨는 것인데요. 녹는 부분만 바꿔주도록 효율적으로 고쳐야 합니다.

감사합니다.

이경로

질문자

제가 코드를 작성할 때 그 부분을 생각해 보았습니다. n의 크기가 최대 100이라 for문을 만번 돌고 main함수의 while문은 모든 칸에 치즈가 꽉 차 있을 경우에 제일 오래 걸릴 테니 최대 49번이라 아무리 오래 걸린다고 해도 49만 번 반복하기 때문에 시간에는 문제가 없는 수준이라고 생각했는데 혹시 반복 횟수가 잘못 계산되었다거나 시간이 더 걸릴 부분이 있을까요?

큰돌

지식공유자

49만 번 반복하기 때문에 시간에는 문제가 없는 수준

>> 네 맞습니다. 그렇게 보면 괜찮은데요.

문제는 시간초과가 났다는 것이고 시간초과를 해결하는 방법은 비효율적인 코드를 개선하는 것뿐입니다. 문제마다 시간초과의 상한선은 각각 다르고 이걸 파악하는 것은 쉽지 않아서요.

이경로

질문자

이제 보니 이 문제의 시간 제한이 1초라서 다른 그래프 문제에 비해 빡빡하네요
앞으로는 문제의 시간도 잘 확인해야겠네요. 감사합니다

인프런 커뮤니티 질문&답변

치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다