소프티어

유령의 위치를 큐에 한번에 넣어 bfs를 수행하는 경우 시간초과가 발생합니다.

하지만 탈출구랑 가장 가까이 있는 유령의 위치를 구하고 해당 위치에서 bfs를 돌고 풀이를 하면 정답처리를 받습니다.

두 경우 모두 시간 복잡도가 O(N^2) 아닌가요?

왜 첫번째 케이스에서 시간초과가 발생하는지 궁금합니다. (두 코드 영역을 제외한 나머지 코드는 동일합니다

1) 모든 유령 위치에서 한번에 bfs

int[][] ghostTime = new int[N][M]; // 유령이 [i,j] 에 도착하는 시간
Arrays.stream(ghostTime).forEach(g -> Arrays.fill(g, Integer.MAX_VALUE));
Queue<int[]> q = new LinkedList<>();
for (int[] x : ghost) {
    q.add(x);
    ghostTime[x[0]][x[1]] = 0;
}

// 유령이 각 {i,j}를 가장 빨리 도착하는 시간을 계산한다.
while (!q.isEmpty()) {
    int[] x = q.poll();
    for (int i = 0; i < 4; i++) {
        int ny = x[0] + dy[i];
        int nx = x[1] + dx[i];
        if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
        if(ghostTime[ny][nx] < ghostTime[x[0]][x[1]] + 1) continue;
        ghostTime[ny][nx] = ghostTime[x[0]][x[1]] + 1;
        q.add(new int[]{ny, nx});
    }
}

2) 가장 짧은 유령에 위치에서만 bfs

  int[][] ghostTime = new int[N][M]; // 유령이 [i,j] 에 도착하는 시간
  Arrays.stream(ghostTime).forEach(g -> Arrays.fill(g, 0x3f3f3f3f));
  Queue<int[]> q = new LinkedList<>();
  int[] minGhost = {0,0}; //목적지까지의 최단 경로에 있는 고스트 위치
  int time = Integer.MAX_VALUE;
  for (int[] x : ghost) {
      int t = Math.abs(x[0] - exit[0]) + Math.abs(x[1] - exit[1]);
      if (time > t) {
          minGhost = x;
          time = t;
      }
  }
  q.add(minGhost);
  ghostTime[minGhost[0]][minGhost[1]] = 0;

  // 유령이 각 {i,j}를 가장 빨리 도착하는 시간을 계산한다.
  while (!q.isEmpty()) {
      int[] x = q.poll();
      for (int i = 0; i < 4; i++) {
          int ny = x[0] + dy[i];
          int nx = x[1] + dx[i];
          if(ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
          if (ghostTime[ny][nx] > ghostTime[x[0]][x[1]] + 1) {
              ghostTime[ny][nx] = ghostTime[x[0]][x[1]] + 1;
              q.add(new int[]{ny, nx});
          }
      }
  }