number-of-islands.md

Number of Islands

Aug 24, 2020 · 7 min read

Дано двумерное поле из нулей и единиц, где 1 означает сушу, а 0 воду. Прилегающие вертикального или горизонтально друг к другу единицы формируют остров.

Нужно найти количество островов.

Задача на LeetCode.

Решение #

По аналогии с задачей про поиск слов поле можно представить как граф.

Получается, что «остров» это вот такой изолированный участок, или disjoint set.

Есть специальная структура данных union-find или disjoint-set, которая помогает организовать такие множества: добавлять, мёрджить и проверять к какому множеству принадлежит элемент. Разберём как можно это использовать для решения задачи чуть позже.

А пока, как можно решить по-простому, без всякой теории графов?

Поиск в глубину #

Бежим по полю. Как только встретили единичку мы знаем, что попали в один из островов. Начнём поиск в глубину, обходя все узлы в графе, при этом не забывая затирать уже посещённые.

Таким образом мы «выкусим» из поля целый остров одной рекурсивной функций. Останется только увеличить счётчик островов после.

Сложность данного решения — линейная относительно количества элементов поля. Действительно, мы можем посетить каждый узел графа только один раз, после мы его «удаляем», а узлов не может быть больше, чем элементов поля.

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  const h = grid.length;

  // если высота поля равна нулю,
  // точно знаем, что и островов
  // там ровно ноль
  if (h === 0) {
    return 0;
  }

  const w = grid[0].length;
  let islands = 0;

  // бежим по всему полю
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      // если встречаем начало «острова»
      if (grid[y][x] === "1") {
        // «выкусываем» его целиком из поля
        burnIsland(grid, w, h, y, x);
        // после чего увеличиваем
        // количество островов на один
        islands++;
      }
    }
  }
  return islands;
};

/**
 * @param {character[][]} grid - поле
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @param {number} y - y-координата текущего узла на поле
 * @param {number} x - x-координата текущего узла на поле
 * @return {number}
 */
function burnIsland(grid, w, h, y, x) {
  // «выкусываем» очередную
  // единичку из острова
  grid[y][x] = "0";

  // бежим по всем четырём направлениям
  // прилегающим вертикально и горизонтально
  for (let [dx, dy] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
    const x1 = x + dx;
    const y1 = y + dy;

    // если следующая координата внутри поля
    within(w, h, y1, x1) &&
      // и если следующая координата внутри острова
      grid[y1][x1] === "1" &&
      // продолжаем рекурсивно «выкусывать»
      burnIsland(grid, w, h, y1, x1);
  }
}

/**
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @param {number} y - y-координата текущего узла на поле
 * @param {number} x - x-координата текущего узла на поле
 * @return {boolean}
 */
function within(w, h, y, x) {
  return 0 <= x && x < w && 0 <= y && y < h;
}

Union-Find #

Union-Find — структура данных, которая поддерживает две операции:

• union объединяет два множества в одно
• find отвечает на вопрос принадлежал ли два узла одному множеству

Про union-find лучше всех рассказывает Роберт Седжвик в курсе на Coursera в деталях, однако для начала можно почитать хороший ответ на Quora.

Чтобы релизовать union-find проще всего завести массив длины размера поля. Каждый возможный узел в графе пронумерован числом от 0 до n - 1, соответственно может храниться в таком массиве.

Сперва подсчитаем количество всех единиц на поле. После пробежим по полю ещё раз и, каждый раз когда встречаем единицу, будем дёргать union для всех соседних единиц. Таким образом формируются множества, как на изображении в начале.

Если удалось соединить узлы (т.е. они ещё не были связаны ранее) — уменьшаем количество единиц. То, что остаётся в итоге и есть количество «островов», потому что в каждом сете есть ровно один узел который окажется связан со всеми соседями ранее (и который мы, в итоге, не отнимем от общего количества).

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  const h = grid.length;

  // если высота поля равна нулю,
  // точно знаем, что и островов
  // там ровно ноль
  if (h === 0) {
    return 0;
  }

  const w = grid[0].length;
  // находим количество всех единиц,
  // в конце здесь будет правильный ответ
  let islands = countAllOnes(grid, w, h);
  // здесь будем хранить связи между узлами
  const store = initStore(w, h);

  // бежим по всему полю
  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      // если встречаем начало «острова»
      if (grid[y][x] === "1") {
        // пробуем объединиться
        // со всеми соседями
        for (const [dx, dy] of [[0, 1], [1, 0], [0, -1], [-1, 0]]) {
          // union вернёт true если
          // объединение прошло успешно
          // и можно уменьшать количество единиц
          if (
            within(w, h, [x + dx, y + dy]) &&
            grid[y + dy][x + dx] === "1" &&
            union(w, h, store, [x, y], [x + dx, y + dy])
          ) {
            islands--;
          }
        }
      }
    }
  }
  return islands;
};

/**
 * @param {character[][]} grid
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @return {number}
 */
function countAllOnes(grid, w, h) {
  let result = 0;

  for (let y = 0; y < h; y++) {
    for (let x = 0; x < w; x++) {
      if (grid[y][x] === "1") {
        result++;
      }
    }
  }
  return result;
}

/**
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @param {number[]} result
 */
function initStore(w, h) {
  return new Array(w * h).fill(0).map((_, index) => index);
}

/**
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @param {number[]} store - хранилище связей
 * @param {number[]} p1 - координаты основной точки на поле
 * @param {number[]} p2 - координаты соседней точки на поле
 */
function union(w, h, store, p1, p2) {
  const id1 = getId(p1, w);
  const id2 = getId(p2, w);
  const root1 = find(store, id1);
  const root2 = find(store, id2);
  // если у них общие родители
  // это означает, что они уже
  // принадлежат одному множеству
  if (root1 === root2) {
    return false;
  }
  // иначе указываем, что у root2 новый родитель:
  // таким образом «цепляем» всё дерево
  // с корнем в root2 к дереву с корнем в root1,
  // формируя disjoint set → наш остров
  store[root1] = root2;
  return true;
}

/**
 * @param {number[]} store - хранилище связей
 * @param {number} id - айдишник узла
 */
function find(store, id) {
  // рекурсивно бежим по родителям,
  // пока не доберёмся до корня дерева
  if (store[id] !== id) {
    return find(store, store[id]);
  }
  return store[id];
}

/**
 * @param {number[]} p - координаты точки на поле
 * @param {number} w - ширина поля
 */
function getId(p, w) {
  // айдишник узла вычисляется
  // как порядковый номер от левого
  // верхнего угла поля
  return p[1] * w + p[0];
}

/**
 * @param {number} w - ширина поля
 * @param {number} h - высота поля
 * @param {number[]} p - координаты точки на поле
 * @return {boolean}
 */
function within(w, h, [x, y]) {
  return 0 <= x && x < w && 0 <= y && y < h;
}

Быстрее ли это? Нет. union работает за линейное время относительно размера поля. Для каждой единички мы дёргаем union. Получаем O(N^2), где N = w * h.

Можно ускорить find и как следствия union с помощью компрессии путей, по которым приходится прыгать find при поиске.

Зачем же тогда писать union-find? Во-первых, это красиво 🙂

А ещё это хорошая задача, чтобы пощупать алгоритм. Потому что есть казалось бы аналогичная задача surrounded regions, но которая хорошо решается через union-find и сложнее через поиск в глубину.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.