3197 - 백조의 호수

작성한 질문수 1

1

안녕하세요 진기님 ㅎㅎ

이 백조의 호수는 시간초과가 까다로운 문제이기도 합니다.

즉, 효율적으로 푸는게 중요해요.

    while(!flag) {
        
        cnt++;
        memset(visit, 0, sizeof(visit));
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(visit[i][j] || m[i][j] == 'X') continue; 
                dfs_w(i, j);
            }
        }

이 코드를 볼까요?

이 코드를 그림으로 그려보면 다음과 같죠?

매번 전체탐색을 해가며 visitied를 초기화하고... 다시 매번... 이렇게 반복되어 초기화된 지점을 탐색해나갑니다.

근데 제 코드를 보시면 해당 지점이 아니라 얼음을 녹인 시점부터 탐색해나가는 것을 볼 수 있습니다.

매번 초기화를 하는 것도 없고 해당 지점부터 하기 때문에 조금 더 빠릅니다.

    while(true){  
        if(move_swan()) break;
        water_melting();
        waterQ = water_tempQ;
        swanQ = swan_tempQ;
        Qclear(water_tempQ);
        Qclear(swan_tempQ);
        day++;
    }

그림으로 그리면 이런 꼴이죠.

조금 더 효율적으로 짜는 것이 중요합니다. 그래서 녹인 지점부터 시작하는 풀루드필로 해야합니다.

또한, 강의 링킹하실 때 해당 문제에다가 부탁드려요. ㅎㅎ

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

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

감사합니다.

강사 큰돌 올림.