3- k 시간복잡도

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요! 정해를 보며 복습중인데

while 문을 통틀어 NxM 맵을 탐색하니 시간복잡도는 O(NxM)이 맞나요?

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

큰돌 · Answer

안녕하세요 ㅎㅎ while 문을 통틀어 NxM 맵을 탐색하니 시간복잡도는 O(NxM)이 맞나요? -> 네 맞습니다.   감사합니다.

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다.

ililil님, 질문 주셔서 감사합니다. 주신 코드에서는 BFS와 같은 탐색이 이루어지고 있기 때문에 시간 복잡도를 고려하는 것이 중요합니다. 질문 주신 부분에 대해 답변을 드리겠습니다.

코드 설명 및 시간 복잡도 분석

move_swan(): 이 함수는 두 백조가 만날 수 있는지 여부를 확인하는 기능으로, BFS 탐색을 사용하여 각 칸을 탐색합니다. 최악의 경우 NxM 크기의 맵 전체를 한 번씩 확인할 수 있습니다.
water_melting(): 물이 얼음을 녹이며 확장하는 기능으로, 마찬가지로 BFS와 유사한 방식으로 인접한 모서리를 순차적으로 녹여갑니다. 이 부분에서도 NxM 크기의 모든 칸을 검사할 수 있습니다.

통합된 시간 복잡도

각 반복마다 두 개의 BFS 탐색 수행이 있으며, 이들이 각각 O(NxM)의 시간 복잡도를 가질 수 있습니다. 따라서 while 루프가 반복되는 횟수만큼 실제 시간 복잡도가 증가할 수 있습니다. 실제로 while 루프는 물이 완전히 얼음에서 녹을 때까지 계속해서 반복되며, 그동안의 복잡도는 다음과 같은 요소에 따라 달라질 수 있습니다:

얼음 녹는 속도: 완전히 녹을 때까지의 걸린 날 수를 기준으로 평가.
백조 이동 가능 경로 확장 속도: 백조가 서로 만나기까지의 경로 확장 시간.

이 모듈들이 개별적으로 실행될 때 O(NxM)의 시간을 필요로 하므로, 전체 운영 시간 복잡도는 문제의 특성 및 데이터에 따라 상당히 많아질 수 있습니다.

위 내용이 도움이 되셨길 바랍니다. 질문하신 내용과 관련해 보다 구체적인 도움이 필요하시다면, 백준 3-K 문제에 대한 기존의 답변 참조하시길 권장드립니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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