2-Q bfs시간초과

작성한 질문수 8

1

안녕하세요 ㅎㅎ

			if(ny < 0 || nx < 0 || ny >= N || ny >= M) continue;

이거 nx >= M 으로 바꿔주세요 ㅎㅎ

다른 부분은 잘 짜신 것 같아요

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

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

감사합니다.

강사 큰돌 올림.

0

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

BFS(너비 우선 탐색)를 사용한 코드가 시간 초과가 나는 문제에 대해 고민하고 계시는군요. 이에 대해 도움을 드릴 수 있는 유사한 질문이 몇 가지 있습니다.

1. 2-B BFS 시간초과 질문

   • 이 질문에서는 시간 초과가 발생하는 이유와 해결 방법에 대해 설명하고 있습니다. 초기화 부분에서 fill 또는 memset 함수를 사용해야 한다고 언급하고 있습니다.
     

2. 3-K 시간초과 질문입니다.

   • 이 질문에서는 함수 호출을 줄여서 시간 초과 문제를 해결하는 방법을 제시합니다.
     

두 링크를 참고하여 BFS 구현에서 개선할 수 있는 부분을 찾으실 수 있을 것입니다. BFS 알고리즘에서 시간초과가 발생할 수 있는 일반적인 원인은 다음과 같습니다:
- 큐를 효율적으로 사용하지 않는 경우
- 불필요하게 상태를 중복 처리하는 경우
- 초기화 과정에서 시간을 많이 소모하는 경우

BFS 알고리즘에서 시간 초과를 방지하려면, 각 상태가 정확히 한 번만 처리되도록 방문 체크를 하고, 큐를 사용한 삽입과 삭제가 올바르게 이루어지는지 확인해야 합니다.

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