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

안녕하세요 원재님 ㅎㅎ

사실 이 치즈문제는 굉장히 효율적으로 푸는 방법이 있습니다.

큐 2개를 사용해서 치즈가 녹은 해당 영역부터 다시 탐색을 시작하는 것이죠.

이부분을 보시면 계속해서 초기화 -> 다시 처음 탐색 시점 부터 탐색을 하기 때문에 효율적이지는 않습니다.

*물론 제 코드도 그러한데 이건 난이도 때문에 그렇게 했습니다.

3주차 때 플루드필을 배우면서 보다 효율적으로 탐색하는 것을 배우니 그 때 한번 그걸 치즈에 적용해보시는것도 좋을 것 같습니다.

    while(true){
        memset(visited, 0, sizeof(visited));
        DFS(0,0);
        ret = chck();

추석 잘보내세요 ㅎ

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

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

감사합니다.

강사 큰돌 올림.

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

원재님께서 질문해주신 내용을 보니, 2-Q 문제를 해결하면서 본인의 코드와 큰돌님의 코드 간의 효율성을 비교하고 계시는군요. 두 코드의 동작 방식과 효율성에 대해 안내 드리겠습니다.

코드 효율성 비교

1. 탐색 방식:

   • 큰돌님의 코드는 DFS를 통해 녹아야 할 치즈 영역을 벡터에 저장하여, 한 번의 탐색으로 필요한 모든 정보를 얻고 있습니다. 이는 이후의 처리 과정을 최소화하여 효율성을 높이는 방법입니다.
     
   • 반면, 원재님의 코드는 DFS 실행 후 별도의 2중 for문을 추가로 돌며 탐색을 수행하셨다고 하셨습니다. 이는 치즈의 상태를 확인하는 과정에서 반복적인 계산이 발생할 수 있어 큰돌님의 방식보다 효율성이 떨어질 수 있습니다.
     

2. 시간 복잡도:

   • 말하신대로 2중 for문을 추가로 사용하면, 불필요한 영역까지 여러 번 탐색하게 될 수 있어 시간 복잡도가 증가할 수 있습니다. 문제의 조건 상, 이런 추가적인 탐색이 큰 영향을 미치지 않을 수 있지만, 최적화는 항상 고려될 필요가 있습니다.
     

3. 제안사항:

   • 가능하다면, DFS를 활용하여 방문 위치에 따라 바로 처리를 수행하는 방식으로 코드 구조를 변경해보는 것이 좋습니다. 즉, DFS 과정에서 필요한 정보를 축적하고 후속 처리는 최소화하는 방향을 지향해보세요.
     

관련하여 비슷한 주제의 다른 질문들을 아래에서 살펴보실 수 있습니다:

• 이 문제 DFS 풀이는 어떤가요?
  
• 2-Q 치즈 질문입니다.
  

이렇게 질문을 통해 다양한 방법을 배우고 적용해보는 것은 알고리즘 실력을 향상시키는 좋은 기회가 될 것입니다.

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