양방향 너비 우선

언어를 고르면 코드가 열린다

def spread(queue, seen, far):
    step = []
    meet = -1
    for cell in queue:
        for other in neighbors(cell):
            if other in seen:
                continue
            seen[other] = cell
            if other in far:
                meet = other
            step.append(other)
    return step, meet


def bidirectional_bfs(start, goal):
    ahead = {start: -1}
    behind = {goal: -1}
    front = [start]
    back = [goal]
    while front and back:
        front, meet = spread(front, ahead, behind)
        if meet < 0:
            back, meet = spread(back, behind, ahead)
        if meet < 0:
            continue
        route = path_to(ahead, meet)
        at = behind[meet]
        while at != -1:
            route.append(at)
            at = behind[at]
        return route
    return []

function spread(queue, seen, far) {
  const step = [];
  let meet = -1;
  for (const cell of queue) {
    for (const other of neighbors(cell)) {
      if (seen.has(other)) continue;
      seen.set(other, cell);
      if (far.has(other)) meet = other;
      step.push(other);
    }
  }
  return [step, meet];
}

function bidirectionalBfs(start, goal) {
  const ahead = new Map([[start, -1]]);
  const behind = new Map([[goal, -1]]);
  let front = [start];
  let back = [goal];
  let meet = -1;
  while (front.length > 0 && back.length > 0) {
    [front, meet] = spread(front, ahead, behind);
    if (meet < 0) {
      [back, meet] = spread(back, behind, ahead);
    }
    if (meet < 0) continue;
    const route = pathTo(ahead, meet);
    for (let at = behind.get(meet); at !== -1; at = behind.get(at)) {
      route.push(at);
    }
    return route;
  }
  return [];
}

int bidirectional_bfs(int start, int goal, int ahead[], int behind[], int n) {
    int* seen[2] = {ahead, behind};
    int* queue[2] = {malloc(sizeof(int) * n), malloc(sizeof(int) * n)};
    int head[2] = {0, 0};
    int tail[2] = {0, 0};
    for (int i = 0; i < n; i++) { ahead[i] = -2; behind[i] = -2; }
    ahead[start] = -1;
    behind[goal] = -1;
    queue[0][tail[0]++] = start;
    queue[1][tail[1]++] = goal;
    int meet = -1;
    int side = 0;
    while (meet < 0 && head[0] < tail[0] && head[1] < tail[1]) {
        int level = tail[side];
        while (head[side] < level) {
            int cell = queue[side][head[side]++];
            for (int d = 0; d < 4; d++) {
                int other = neighbor(cell, d);
                if (other < 0 || seen[side][other] != -2) continue;
                seen[side][other] = cell;
                if (seen[1 - side][other] != -2) meet = other;
                queue[side][tail[side]++] = other;
            }
        }
        side = 1 - side;
    }
    free(queue[0]);
    free(queue[1]);
    return meet;
}

static int spread(std::vector<int>& queue,
                  std::unordered_map<int, int>& seen,
                  const std::unordered_map<int, int>& far) {
    std::vector<int> step;
    int meet = -1;
    for (int cell : queue) {
        for (int other : neighbors(cell)) {
            if (seen.count(other) > 0) continue;
            seen[other] = cell;
            if (far.count(other) > 0) meet = other;
            step.push_back(other);
        }
    }
    queue = step;
    return meet;
}

std::vector<int> bidirectional_bfs(int start, int goal) {
    std::unordered_map<int, int> ahead{{start, -1}};
    std::unordered_map<int, int> behind{{goal, -1}};
    std::vector<int> front{start};
    std::vector<int> back{goal};
    while (!front.empty() && !back.empty()) {
        int meet = spread(front, ahead, behind);
        if (meet < 0) meet = spread(back, behind, ahead);
        if (meet < 0) continue;
        std::vector<int> route = path_to(ahead, meet);
        for (int at = behind[meet]; at != -1; at = behind[at]) {
            route.push_back(at);
        }
        return route;
    }
    return {};
}

static int Spread(List<int> queue, Dictionary<int, int> seen,
                  Dictionary<int, int> far) {
    var step = new List<int>();
    int meet = -1;
    foreach (int cell in queue) {
        foreach (int other in Neighbors(cell)) {
            if (seen.ContainsKey(other)) continue;
            seen[other] = cell;
            if (far.ContainsKey(other)) meet = other;
            step.Add(other);
        }
    }
    queue.Clear();
    queue.AddRange(step);
    return meet;
}

static List<int> BidirectionalBfs(int start, int goal) {
    var ahead = new Dictionary<int, int> { [start] = -1 };
    var behind = new Dictionary<int, int> { [goal] = -1 };
    var front = new List<int> { start };
    var back = new List<int> { goal };
    while (front.Count > 0 && back.Count > 0) {
        int meet = Spread(front, ahead, behind);
        if (meet < 0) meet = Spread(back, behind, ahead);
        if (meet < 0) continue;
        var route = PathTo(ahead, meet);
        for (int at = behind[meet]; at != -1; at = behind[at]) {
            route.Add(at);
        }
        return route;
    }
    return new List<int>();
}

static int spread(List<Integer> queue, Map<Integer, Integer> seen,
                  Map<Integer, Integer> far) {
    List<Integer> step = new ArrayList<>();
    int meet = -1;
    for (int cell : queue) {
        for (int other : neighbors(cell)) {
            if (seen.containsKey(other)) continue;
            seen.put(other, cell);
            if (far.containsKey(other)) meet = other;
            step.add(other);
        }
    }
    queue.clear();
    queue.addAll(step);
    return meet;
}

static List<Integer> bidirectionalBfs(int start, int goal) {
    Map<Integer, Integer> ahead = new HashMap<>();
    Map<Integer, Integer> behind = new HashMap<>();
    ahead.put(start, -1);
    behind.put(goal, -1);
    List<Integer> front = new ArrayList<>(List.of(start));
    List<Integer> back = new ArrayList<>(List.of(goal));
    while (!front.isEmpty() && !back.isEmpty()) {
        int meet = spread(front, ahead, behind);
        if (meet < 0) meet = spread(back, behind, ahead);
        if (meet < 0) continue;
        List<Integer> route = new ArrayList<>(pathTo(ahead, meet));
        for (int at = behind.get(meet); at != -1; at = behind.get(at)) {
            route.add(at);
        }
        return route;
    }
    return List.of();
}