3-K 질문있습니다.!

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

3-K와 문제의 단순화

작성

400

처음 오리의 위치를 딱 정해서 오리의 처음 위치 부터 계속 탐색 시켰습니다.
이러니 시간 초과가 나오게 되었습니다.
왜 시간 초과가 나오는지 궁금합니다.

https://www.acmicpc.net/source/61456336
while (true){

ans++;

v.clear();

find_water();

ice_break();

if (find_duck()) break;

}

이 부분에서 find_water가 O(1500*1500) 이정도 시간이 걸린다고 생각합니다.
호수의 크기가 1500x1500이고 오리가 (0,0), (1500,1500)에 있을때, 대충 bfs로 정점이 1500개, 간선이 4개니까, O(1500 + 4)정도 걸린다고 생각합니다.

O(1500*1500) * O(1500)이라 시간 초과가 나는것이라고 생각하는데, 이렇게 계산하는것이 맞는지 궁금합니다.
영상에서 나온 방법은 왜 시간초과가 안 나오는지도 궁금합니다...

문제 해설과 똑같은 로직으로 코드를 짜보았습니다.

https://www.acmicpc.net/source/61457241

하지만, 메모리 초과가 나와 질문합니다..

어디가 메모리가 초과되는지 알고 싶습니다!

c++코딩-테스트

답변 3

큰돌

지식공유자

안녕하세요 동훈님 ㅎㅎ

동훈님이 짜신 코드는 처음부터 계속해서 탐색을 이어가는 것이죠.

void ice_break(){
    queue<pair<int,int>> q;
    memset(visited,false, sizeof(visited));

    for (pair<int,int> p : v){
        visited[p.first][p.second] = true;
        q.push(p);
    }

    while(!q.empty()){
        pair<int,int> now = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++){
            int my = now.first + ay[i];
            int mx = now.second + ax[i];

            if (mx <= 0 || mx > C || my <= 0 || my > R) continue;
            if ( A[my][mx] == 'X'){
                A[my][mx] = '.';
                visited[my][mx] = true;
                continue;
            }
            if (visited[my][mx]) continue;
            
            q.push({my,mx});
            visited[my][mx] = true;
        }



    }

}

제 코드와 비교하면 다음과 같은 부분이 다릅니다.

위에 그림은 동훈님 코드, 아랫부분은 제 코드입니다. 불필요한 탐색이 들어가서 시간초과가 난다고 보시면 됩니다.

호수의 크기가 1500x1500이고 오리가 (0,0), (1500,1500)에 있을때, 대충 bfs로 정점이 1500개, 간선이 4개니까, O(1500 + 4)정도 걸린다고 생각합니다.

O(1500*1500) * O(1500)이라 시간 초과가 나는것이라고 생각하는데, 이렇게 계산하는것이 맞는지 궁금합니다.

>> 얼핏 맞긴합니다만, 정확히 계산해보면 다음과 같습니다.

맵의 너비 만큼 bfs가 일어납니다. O(1500 * 1500)이죠.

동훈님의 코드는 이 bfs를 빙판이 다 녹을 때까지 계속해서 반복하고 있습니다.

모든 칸이 빙판으로 이루어졌다고 가정하면 최대 750입니다.

즉,

1500 곱하기

750입니다.

즉, 1,687,500,000 의 시간복잡도를 가집니다.

그래서 시간초과가 나는 것 같습니다.

그러나 계속해서 BFS를 탐색하는게 아니라 녹은 칸수를 기반으로 BFS를 한번만 돌리게 되면

1500 곱하기 1500

즉, 2,250,000의 시간복잡도로 풀리게 되는 것입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

김동훈

질문자

메모리 초과 케이스는 입력값을 잘못 받았을 뿐더러,
얼음이 녹는 로직, 백조가 이동하는 로직에서 방문처리, 큐에 넣는 로직을 잘못 구현해서 무한 루프? 가 돌아서 메모리 초과가 나온것 같네요..

김동훈

질문자

bfs로 탐색하면 칸수만큼 탐색하게 되니 O(1500*1500)이고
처음 위치에서 계속 탐색하게 되니
(1500/2) x 1500 x 1500 이군요...
답변 감사합니다!!

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

3-K 질문있습니다.!