TimeLimit 문의 드립니다

로직은 다르지만 의미는 강의와 비슷하게 구현한듯 한데 타임리밋이 발생하여 문의 드립니다. 어떤 부분이 잘못된 걸까요?

public class 송아지찾기 {

   int count = 0;
   boolean visited[] = new boolean[10001];

   public int BFS(int s ,int e) {
      Queue<Integer> queue = new LinkedList<>();
      queue.add(s);

      while (!queue.isEmpty()) {
         int size = queue.size();

         for (int i = 0; i < size; i++) {
            Integer poll = queue.poll();
            visited[poll] = true;



            if (poll + 1 < 1000 && !visited[poll + 1]) {
               if (poll + 1  == e) {
                  return count + 1;
               }
               queue.add(poll + 1);
            }

            if (poll + 5 < 10000 && !visited[poll + 5]) {
               if (poll + 5  == e) {
                  return count + 1;
               }
               queue.add(poll + 5);
            }

            if (poll - 1 > -1 && !visited[poll - 1]) {
               if (poll -1   == e) {
                  return count + 1;
               }
               queue.add(poll - 1);
            }
         }

         count++;
      }

      return count;
   }

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

님의 코드를 살펴보았을 때, 타임 리밋(TimeLimit)이 발생하는 주된 이유는 큐(Queue)에 중복된 위치가 추가되기 때문일 가능성이 높습니다. 이를 방지하기 위해서는 위치를 Queue에 추가할 때, 그 위치를 방문했다고 표시하는 visited[poll + 1], visited[poll + 5], visited[poll - 1] 등을 queue.add()하기 전에 해주어야 합니다.

또한 poll + 1 < 1000과 poll + 5 < 10000 조건에서, 1000은 10000으로 수정해야 올바르게 범위를 체크할 수 있습니다. 탐색 범위가 제대로 설정되지 않으면 예상치 못한 문제가 발생할 수 있습니다.

수정된 부분을 반영한 코드는 다음과 같습니다:

public class 송아지찾기 {

   int count = 0;
   boolean visited[] = new boolean[10001];

   public int BFS(int s ,int e) {
      Queue<Integer> queue = new LinkedList<>();
      queue.add(s);
      visited[s] = true; // 시작 지점을 방문 표시

      while (!queue.isEmpty()) {
         int size = queue.size();

         for (int i = 0; i < size; i++) {
            Integer poll = queue.poll();

            if (poll == e) { // 목표지점 도달 확인
                return count;
            }

            if (poll + 1 < 10000 && !visited[poll + 1]) { // 1000 -> 10000 수정
               visited[poll + 1] = true; // 방문 표시
               queue.add(poll + 1);
            }

            if (poll + 5 < 10000 && !visited[poll + 5]) {
               visited[poll + 5] = true; // 방문 표시
               queue.add(poll + 5);
            }

            if (poll - 1 > -1 && !visited[poll - 1]) {
               visited[poll - 1] = true; // 방문 표시
               queue.add(poll - 1);
            }
         }

         count++;
      }

      return count;
   }

if (poll + 1 == e), if (poll + 5 == e), if (poll -1 == e) 조건을 큐에서 원소를 꺼낼 때 바깥쪽 루프에 배치하여 더 이른 시점에 목적지에 도달했는지 확인할 수 있습니다. 이렇게 수정하면 중복되는 위치를 큐에 추가하는 문제를 줄이고, 탐색의 효율성을 높여 타임 리밋 문제를 해결할 수 있습니다.

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