2 - P 시간복잡도 질문

작성한 질문수 16

0

안녕하세요 ㅎㅎ

    for(pair<int, int> b : virusList){
        visited[b.first][b.second] = 1;
        dfs(b.first, b.second);
    } 

    int cnt = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 0 && !visited[i][j])cnt++;
        }
    } 

이부분이 64 + 64 부분인데요.

먼저 모든 경우의수 에 해당하여

dfs(모든 정점을 탐색 = 64) 그리고 나서

카운팅(모든 정점에 대해 cnt++인지를 체크) 하기 때문에 64 + 64가 됩니다.

만약에

DFS 후에 그것에 대해서 또 넓이 계산

-> 이라는 로직이라면 DFS를 호출할 때마다 넓이 계산이 들어가야 하므로 DFS 안에서 넓이 계산 로직이 들어가야 합니다.

감사합니다.

0

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

질문 하신 내용은 시간 복잡도 계산과 관련된 부분으로 보입니다. 이 문제에서, 강사님께서 제공하신 시간 복잡도는 각각의 단계가 어떻게 실행되는지를 분석하며 결정되었을 것입니다.

• 독립적인 계산은 하나의 큰 반복문이나 경우의 수를 다루기 위한 전반적인 계산을 나타냅니다. 이 경우 64 * (64 + 64)라고 표현된 것은 먼저 벽 세우기 완탐을 64회 시도하고, 그 후에 각 경우에 대해 DFS 탐색(64)과 연결 컴포넌트 넓이 계산(64)을 독립적으로 수행한다는 것을 의미합니다.

• 64 * 64 * 64이라면, 각 벽 세우기에 대해 모든 경우를 다시 탐색한 후 결과를 계산하는 방식일 것입니다. 따라서 여기서는 각각 독립적인 과정을 별도로 수행하는 ‘독립 + 종속’의 형태로 분석하신 것이 맞다고 판단됩니다.

마치 하나의 벽 세우기 시도에 대해 두 가지 서로 다른 연산 과정(DFS와 넓이 계산)이 담겨 있는 것처럼 각 방식이 계산된 것입니다.

비슷한 질문이 다음 링크에서 다루어지고 있으니, 확인해 보시면 더 도움이 될 수 있습니다: 시간 복잡도와 알고리즘 효율성 관련 질문

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