Inflearn Community Q&A

안녕하세요 남궁근님 ㅎㅎ

	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){	

이부분에서 아래 for문은 j < M이 아닐까요?

이부분을 고쳐보시겠어요?

감사합니다.

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

2636번 치즈 문제와 관련한 시간 초과 이슈에 대해 고민하고 계시군요. 치즈 문제는 다양한 방법으로 풀 수 있지만, DFS나 BFS를 사용하는 방식이 대개 효율적입니다. 행렬을 두 개 사용하는 방식에서 가장 흔한 문제는 불필요한 탐색으로 인한 시간 초과입니다.

• BFS/DFS 활용: 일반적으로 치즈를 탐색하고 녹이는 문제는 BFS나 DFS를 사용하여 효율적으로 해결할 수 있습니다. 공기와 닿아있는 치즈를 우선적으로 녹인 후, 그 상태를 기반으로 다시 탐색하는 방식이 효과적입니다.

• 기초 최적화 팁:

  1. 치즈가 있는 좌표만 따로 저장 후 업데이트를 하여 모든 좌표를 매번 검사하지 않도록 개선할 수 있습니다.
     
  2. BFS를 사용하여 바로 치즈를 녹이는 것이 아니라, 다음 라운드에 녹아야 할 치즈를 저장하고, 한 번에 여러 개의 치즈를 지우는 방식이 더 효율적일 수 있습니다.
     
  3. DFS/BFS 탐색 후 방문여부 체크를 잘 활용하여 불필요한 반복 탐색을 막을 수 있습니다.
     

유사한 사례나 해결 방법을 다룬 질문들이 있습니다. 다음 링크에서 참고하시면 도움이 될 것 같습니다:

• 치즈 녹이는 로직을 벡터 없이 구현했는데 시간 초과가 발생합니다
  
• 2636 치즈 질문드립니다
  

각 링크에서는 최적화 및 이상적인 방법에 대한 설명과 코드 예제가 제공됩니다.

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