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

안녕하세요 ㅎㅎ

거의 다 괜찮은데 이부분, 방문 여부와 상관없이 DFS 콜이 비효율적인 것 같습니다.

바로 요부분이죠 ㅎㅎ

사실은 방의 크기가 50이하이기 때문에 -> 2500이 최대범위라 시간복잡도상 그렇게 큰 차이는 없지만 만약 최대범위가 커진다면 반드시 고쳐야 하는 코드이기도 합니다.

이부분을 이렇게 바꿔보시겠어요?

void DFS(int y, int x){
    visited[y][x] = 1;
    cnt++;
    for(int i = 0; i < 4; i++){
        if ((field[y][x] & (1 << i)) == 0) {
            int ny = y, nx = x;
            if (i == 0) nx = x - 1;        // 서
            else if (i == 1) ny = y - 1;   // 북
            else if (i == 2) nx = x + 1;   // 동
            else if (i == 3) ny = y + 1;   // 남

            if (ny >= 0 && ny < m && nx >= 0 && nx < n && !visited[ny][nx]) {
                DFS(ny, nx);
            }
        }
    }
}

int go(){
    memset(visited, 0, sizeof(visited));
    int answer = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if (!visited[i][j]) {      // 이 조건 해야되용
                cnt = 0;
                DFS(i, j);
                answer = max(answer, cnt);
            }
        }
    }
    return answer;
}

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

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

감사합니다.

강사 큰돌 올림.

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

효율성 측면에서 작성하신 코드와 큰돌님의 코드가 어떤 차이를 보이는지 궁금하시다면, 몇 가지 주요 관점을 고려해 볼 수 있습니다.

코드 효율성 비교 방법

1. 시간 복잡도: 코드의 핵심 루프가 얼마나 자주 돌아가며, 주어진 입력 크기에 대해 얼마나 효율적으로 처리되는지 확인합니다. 큰돌님의 코드와 비교하여 반복문이나 조건문이 더 많이 사용되고 있는지 확인해 보세요.

2. 공간 복잡도: 사용하신 자료 구조가 메모리 효율을 잘 고려하고 있는지, 불필요한 메모리 사용이 없는지 따져 보세요.

3. 사용된 알고리즘: 동일한 문제를 풀 때, 큰돌님과 다른 알고리즘적 접근을 하셨다면, 그 알고리즘이 문제에 대해 최적화된 해법인지 검토합니다.

이와 관련한 유사 질문 및 답변

• 코드 효율성 질문드려요: 이 질문에서는 시간 복잡도 분석 및 로그리즘 관련 최적화 방법이 포함된 답변을 참조할 수 있습니다.
  
• 효율적인 해킹 코드 질문: 그래프 탐색 알고리즘을 사용한 시간 복잡도 최적화에 대해 설명하고 있습니다.
  

이런 내용을 바탕으로 자신의 코드와 큰돌님 코드를 비교 검토해 보시면, 효율성 측면에서 어떤 개선점이 있는지 확인하실 수 있을 것입니다.

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