El problema Shortest Bridge plantea un reto clásico de grafos: dado un mapa con dos islas, encontrar la menor cantidad de material necesaria para construir un puente que las conecte. Aprenderás a combinar DFS y BFS para resolverlo paso a paso, una técnica útil si te preparas para entrevistas técnicas o estudias estructuras de datos.

El mapa se representa como una matriz de ceros y unos, donde el cero es agua y el uno es tierra. Tu meta es calcular la distancia más corta entre las dos islas y devolver cuántas casillas de agua necesitas atravesar para unirlas.

¿Cómo identificar la primera isla con DFS?

El primer subproblema consiste en detectar dónde empieza y termina una de las islas. Aquí entra en juego Depth First Search, una técnica que ya hemos trabajado en el módulo de DFS para encontrar islas en una matriz.

La idea es simple: recorres la matriz hasta encontrar el primer uno, y desde ahí profundizas hacia sus casillas adyacentes mientras sigan siendo tierra. Mientras avanzas, vas guardando los bordes de la isla en un stack, porque esos bordes serán tu punto de partida para la siguiente fase.

¿Por qué usar DFS para encontrar la primera isla? Porque DFS te permite recorrer todas las casillas conectadas de la isla y registrar sus bordes, que son justamente las casillas desde donde tendrás que empezar a tender el puente.

¿Cómo encontrar la distancia más corta con BFS?

Una vez tienes los bordes de la primera isla, necesitas avanzar hacia la segunda usando la menor cantidad de pasos posibles. Aquí es donde Breadth First Search brilla, porque explora nivel por nivel y garantiza encontrar el camino más corto [02:30].

Tu cola de BFS no inicia con un solo punto, sino con todas las coordenadas del borde de la primera isla. Desde ahí avanzas en todas las direcciones adyacentes (arriba, abajo, izquierda, derecha) hacia las casillas de agua. Cada nivel completo de expansión equivale a una unidad de material del puente.

Para evitar revisitar casillas, conviene usar un hash set donde guardas las coordenadas ya exploradas. El hash set tiene mejor complejidad de búsqueda que una lista, así que verificar si una casilla ya fue visitada se vuelve eficiente.

¿Cuándo se detiene el BFS?

El recorrido se detiene en el momento en que tu casilla actual tiene valor uno, lo que significa que tocaste la segunda isla. En ese punto retornas la cantidad de niveles que recorriste por el agua.

¿Qué retorna exactamente el algoritmo? La cantidad de niveles recorridos menos uno, porque el último salto ya cae sobre tierra y no cuenta como material del puente.

Este detalle es fácil de pasar por alto. Si haces dos saltos pero el segundo aterriza en la otra isla, la distancia real del puente es de uno, no de dos.

¿Por qué combinar DFS y BFS en el mismo problema?

La combinación funciona porque cada técnica resuelve una mitad distinta del problema. DFS es ideal para mapear una región conectada (la primera isla y sus bordes), mientras que BFS es óptimo para calcular distancias mínimas en una matriz sin pesos.

Algunos puntos clave para tener presentes al implementar la solución:

• Inicializa la cola del BFS con todas las coordenadas del borde de la primera isla, no con una sola.
• Usa un hash set para registrar casillas visitadas y evitar ciclos.
• Avanza únicamente por casillas con valor cero (agua).
• Detén el BFS cuando encuentres una casilla con valor uno.
• Retorna el número de niveles menos uno como respuesta final.

¿Podrías invertir el orden y usar primero BFS para detectar la isla y luego DFS para encontrar la distancia más corta? Deja tu respuesta en los comentarios, junto con tu análisis de la complejidad temporal y espacial de esta solución. Nos vemos en la siguiente clase para implementarlo en código.